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

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

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

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

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

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

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

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

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

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