移動對象數據庫中時空數據管理若干關鍵技術研究.pdf

1、隨著GPS定位、無線技術和計算機技術的迅猛發(fā)展，越來越多的移動對象被實時存儲在數據庫中，而傳統(tǒng)數據庫都是以優(yōu)化靜態(tài)數據查詢?yōu)槟繕耍@促使以管理表示頻繁更新移動對象的時空數據為目標的移動對象數據庫的產生。由于傳統(tǒng)數據庫技術都無法支持對時空數據的有效管理，因此，需要對移動對象數據庫的相關技術進行研究。
　　 本文主要從兩個方面研究了移動對象數據庫中時空數據管理的關鍵技術問題。一是時空數據索引技術。在這方面，本文主要探討和研究了公路網

2、絡環(huán)境下時空數據的索引技術；二是軌跡數據(歷史時空數據)的異常點檢測算法。在這方面，本文主要研究了由具有較長路徑的軌跡組成的軌跡數據的異常點檢測算法。
　　 在索引技術方面，本文針對更新操作在公路網絡環(huán)境下的新特點，提出了一種支持頻繁更新的時空數據索引結構GTR-Tree(Group Updateand Time Parameter R-Tree)。該索引結構先對公路網路的邊建立R-Tree索引，然后再對移動對象進行索引，移動對

3、象在邊上的位置用x坐標或y坐標表示，并引入時間函數以避免勻速運動的更新。這樣，在公路網絡環(huán)境下，按照更新前后移動對象所處邊的不同，把更新操作分成跨邊更新(更新后移動對象位于不同的公路)、勻速更新(更新前后對象不僅處在同一條公路，而且對象還處在勻速運動)和非勻速更新(更新前后對象處在同一公路，但不是勻速運動)三類；那么針對不同的更新類型執(zhí)行不同的更新過程，如勻速更新可以直接被省略。同時，在R-Tree的葉子結點附上內存緩沖以緩存新插入數據

4、項，僅當該緩沖區(qū)滿時，將最大分組的緩沖數據項刷新到對應的磁盤空間以共享磁盤I/O，而刪除信息則有一個常駐內存的過期對象表維護，直到該某條邊所在存儲區(qū)域被訪問時才刪除里面的過期數據項。過期對象表的存在使得GTR-Tree的CPU性能很低，為了解決這個問題，本文對GTR-Tree進行改進，提出了一種新的索引結構MGTR-Tree，該索引結構將更新操作分成兩個子操作：插入子操作向索引結構插入一個新數據插入的數據項，而刪除子操作則是向索引結構插

5、入一個刪除舊數據的子操作。通過這個方式，MGTR-Tree的數據結構可以刪除過期對象表，從而保證了算法在CPU代價的高效性。此外，GTR-Tree和MGTR-Tree組更新技術都要借助于內存空間作為緩沖才能實現(xiàn)，因此，本文還提出了另一種在公路網絡環(huán)境下實現(xiàn)組更新技術的索引結構DGTR-Tree。該索引結構以磁盤介質為緩沖區(qū)實現(xiàn)組更新技術，它不需要任何內存空間作依托，從而提高了組更新技術的適用性。該索引結構在R-Tree的每個結點附上一個

6、緩沖區(qū)，屬于某個結點的數據項先緩存在該結點對應的緩沖區(qū)中，僅當該緩沖區(qū)滿時，才將該緩沖區(qū)內的數據項刷新到對應的子結點中，從而實現(xiàn)訪問共享。
　　 在軌跡數據異常點檢測方面，一方面，本文針對當前異常軌跡檢測算法只比較軌跡形狀的不足，詳細分析了軌跡數據與圖像數據的不同以及軌跡數據中隱含的一些固有特征，提出了一種新的衡量軌跡片段相似度的度量方法，該度量方法采用基于平移的最小Hausdorff距離的思想，結合軌跡數據本身的固有特征，從軌

7、跡片段的形狀和其蘊含的局部運動模式(移動速度和移動方向)兩個角度進行軌跡片段相似度的比較；并在此基礎上，定義了相近基本軌跡單元對(一個軌跡片段中的點屬于另一個軌跡片段對應點的鄰域內)、異常軌跡的概念；并提出了一種基于R-Tree的異常軌跡檢測算法，該算法首先對所有軌跡點建立一個R-Tree索引，然后利用R-Tree搜索出每個軌跡點的對應的鄰域點子集，再利用兩條軌跡間的點距離特征矩陣(兩條軌跡中每兩個點組合為元素組成的矩陣)快速找出所有相

8、近的基本軌跡單元對，從而提高算法的搜索性能。另一方面，隨著用戶需求的提高，不僅軌跡數據在變大，而且組成軌跡的點數目也在不斷變多(軌跡時間跨度變大和精度提高都會增加點數)。針對越來越長的軌跡，以一條軌跡為單位的檢測結構(軌跡是否為異常軌跡)已經不能滿足一些特定用戶的需要。本文提出了一種以軌跡點為目標的軌跡數據異常點檢測算法，該算法給每個軌跡點賦予一個表示其局部異常程度的值，即局部異常度(Local Outlier Degree，簡稱LOD

9、)。這里的“局部”包含兩層含義：一、軌跡間的比較是以軌跡片段為基礎進行比較；二、軌跡片段僅與其一定鄰域內的軌跡片段進行比較。軌跡點的局部異常度是基于固定長度的軌跡片段為基礎，通過該點在軌跡片段中的異常程度。
　　 本文對提出的各種算法不僅都作了詳細的性能分析，而且使用實際數據集或綜合數據集對算法進行了詳細實驗。索引結構方面使用的實驗數據集是使用Oldenbourg實際公路網絡數據和基于網絡的數據生成器生成的綜合數據，而對于軌跡數