移動對象連續(xù)κ近鄰查詢處理技術(shù)研究.pdf

1、基于位置的服務(wù)(LBS)是指通過移動終端和無線通訊網(wǎng)絡(luò)的配合，確定用戶具體所在的空間位置，從而為用戶提供與空間位置相關(guān)的信息服務(wù)，如導(dǎo)航服務(wù)、交通調(diào)度、物流管理、緊急呼叫、位置廣告等。基于位置的服務(wù)通常涉及到對大量移動對象的查詢，k近鄰(kNN)查詢就是其中最為重要的查詢之一。
　　 七近鄰查詢在解決實際應(yīng)用中的需求越來越明顯，引起了相關(guān)研究領(lǐng)域的廣泛關(guān)注。目前，針對歐式空間中靜態(tài)對象的k近鄰查詢技術(shù)已發(fā)展成熟，對于道路網(wǎng)環(huán)境，

2、且考慮移動對象的連續(xù)七近鄰(CkNN)查詢處理技術(shù)的研究還很少，且已有的查詢處理技術(shù)在面對大量并發(fā)查詢時，效果并不太理想。
　　 本文是針對道路網(wǎng)環(huán)境下的移動對象連續(xù)七近鄰查詢處理技術(shù)展開的研究，目的在于盡可能地提高服務(wù)器端的查詢處理效率，從而縮短查詢響應(yīng)時間。所做的工作主要體現(xiàn)在以下幾個方面:
　　 (1)深入剖析了已有的基于歐式空間的和道路網(wǎng)環(huán)境下的移動對象連續(xù)k近鄰查詢處理的經(jīng)典算法，對其一般性技術(shù)思路進(jìn)行了概括，

3、并討論了各種查詢處理方法的優(yōu)缺點(diǎn)。比較了道路網(wǎng)環(huán)境和歐式空間查詢處理的不同，總結(jié)了道路網(wǎng)環(huán)境下七近鄰查詢處理的難點(diǎn)。
　　 (2)經(jīng)分析道路網(wǎng)環(huán)境下k近鄰查詢的特點(diǎn)，設(shè)計了一種共享計算的初始結(jié)果計算算法，在查詢處理中，充分復(fù)用其他查詢的計算成果，從而避免了對道路網(wǎng)的冗余搜索。實驗驗證了該算法在查詢密集型道路網(wǎng)中的高效性。
　　 (3)面向高度動態(tài)的道路網(wǎng)環(huán)境，提出了一種基于擴(kuò)展樹的連續(xù)k近鄰查詢處理方法(TL-CkNN)