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

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

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

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

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

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