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

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

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

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

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

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