路網(wǎng)中的k最近鄰軌跡查詢方法研究.pdf

1、隨著無線通信、移動(dòng)計(jì)算以及位置定位等相關(guān)技術(shù)日趨成熟，人們對移動(dòng)信息的需求急劇增長使得位置相關(guān)服務(wù)走進(jìn)我們的日常生活。近年來，研究者們對位置相關(guān)查詢，特別是最近鄰查詢進(jìn)行了深入的研究，提出了許多有效的查詢處理方法?？臻g數(shù)據(jù)庫中的相關(guān)查詢可以分為兩類:一類是基于歐式空間的查詢，另一類是基于路網(wǎng)的查詢;從應(yīng)用角度看，針對路網(wǎng)的查詢更具有實(shí)際應(yīng)用價(jià)值。因此，對于路網(wǎng)中如何快速高效地找到k最近鄰軌跡的查詢方法的研究迫在眉睫。
　　本文提出

2、了帶更新的k聚集最近鄰軌跡查詢方法（aggregate k nearest neighbortrajectory query method which can update the results，UANNT），同時(shí)針對在傾斜數(shù)據(jù)集上，候選軌跡集合生成緩慢的情況，提出分組k最近鄰查詢算法（grouping k nearest neighbortrajectory query algorithm，k-GNNT）以及基于限定生成的k最近鄰查

3、詢算法（qualifiers-based k nearest neighbor trajectory query algorithm，k-ANNT*）。本文主要貢獻(xiàn)如下:
　　首先，本文提出了帶更新的k最近鄰查詢方法。其中查詢軌跡由節(jié)點(diǎn)集表示，通過候選生成和候選驗(yàn)證得到軌跡的k最近鄰軌跡。在用戶按查詢軌跡移動(dòng)過程中，使用算法對結(jié)果進(jìn)行更新，在不增加額外候選軌跡的前提下，得到關(guān)于用戶余下軌跡的k最近鄰軌跡。
　　其次，傾斜數(shù)據(jù)

4、集中查詢軌跡包含異常點(diǎn)，會(huì)造成全局最小堆內(nèi)匹配對彈出受阻。因?yàn)槿肿钚《训淖枞樵兒蜻x軌跡集合生成緩慢，當(dāng)查詢點(diǎn)數(shù)目過大時(shí)，查詢性能將受到更大影響。針對這一情況本文提出兩種方法解決，分別是分組k最近鄰查詢算法和基于限定生成的k最近鄰查詢算法。其中分組算法主要通過對查詢軌跡節(jié)點(diǎn)分組來降低全局最小堆的規(guī)模，緩解堆內(nèi)匹配對堵塞狀況，再通過評(píng)價(jià)函數(shù)找到查詢軌跡的k條最近鄰軌跡?；谙薅ㄉ伤惴ê诵氖峭ㄟ^補(bǔ)全軌跡的缺失匹配對，生成更為緊湊的候選