受限路網(wǎng)中移動對象雙層索引結構研究.pdf

1、近年來，作為移動計算技術的重要分支以及基于位置的服務的支撐技術之一，移動對象數(shù)據(jù)庫正受到越來越多的重視，眾多學者與機構開始投入大量精力在這個領域進行研究。移動對象數(shù)據(jù)庫系統(tǒng)中存放著大量的關于移動對象位置信息的時空軌跡數(shù)據(jù)，受到主客觀因素的影響，移動對象運行行為具有動態(tài)性、不確定性和實時性的特點，需要不斷更新位置信息。為了支持對不確定性移動對象過去及當前位置的查詢，必須提供更加有效和高效的索引結構。對移動對象的位置信息進行高效索引和查詢，

2、在地理信息系統(tǒng)和智能導航、實時跟蹤、精確定位技術方面具有很高的應用價值和研究意義。當前國內外的索引算法或者主要考慮索引建立和維護時的效率，或者考慮基于索引進行查詢時的準確性，對索引建立和維護時的性能以及查詢時性能綜合考慮的算法較少。本文針對當前熱點索引方法:NDTR-tree(network-constrained moving objects dynamic trajectory R-tree)和FNR-tree(fiexed net

3、work R-tree)進行了介紹和實現(xiàn)，并分析了兩種算法的優(yōu)缺點。
　　 本文旨在對當前路網(wǎng)移動對象軌跡索引方法進行深入研究，從索引的建立和維護以及范圍查詢時的性能方面進行提高。提出新型的索引方法HNTR-tree(Hierarchical Network-constraint moving objects Trajectory R-tree)，對靜態(tài)路網(wǎng)信息采用R*-tree索引管理，對實時更新的移動對象運動軌跡采用節(jié)點更新

4、代價較小的R-tree進行索引，并利用哈希表和雙向鏈表協(xié)同管理。相比于NDTR-tree，HNTR-tree不僅在索引建立和維護操作上提高了效率，而且極大地提高了移動對象軌跡查詢的效率。
　　 本文的主要工作如下:
　　 (1)提出了一種新型受限路網(wǎng)中移動對象雙層索引結構HNTR-tree，詳細闡述了HNTR-tree的索引結構及HNTR-tree的索引建立和維護算法，并給出移動對象的不確定性軌跡刪除算法和移動對象時空范

5、圍查詢算法。
　　 (2)國內外相關研究大多采用Oldenbourg或者San Jose路網(wǎng)數(shù)據(jù)集，該數(shù)據(jù)集中，路網(wǎng)由邊組成而不是道路組成。本文通過對成都市真實矢量地圖采集點生成數(shù)據(jù)集，使路網(wǎng)數(shù)據(jù)考慮真實的道路（現(xiàn)實情況下一條道路可能含有多個邊）。進行大量實驗，詳細比較HNTR-tree、NDTR-tree、FNR-tree在索引的建立和維護、移動對象軌跡查找、時空范圍查詢方面的性能。通過對成都市真實矢量地圖數(shù)據(jù)集進行實驗，結果