移動(dòng)對(duì)象數(shù)據(jù)庫中時(shí)空數(shù)據(jù)管理若干關(guān)鍵技術(shù)研究.pdf

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

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

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

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

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

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

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

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

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