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

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

2、且考慮移動(dòng)對(duì)象的連續(xù)七近鄰(CkNN)查詢處理技術(shù)的研究還很少，且已有的查詢處理技術(shù)在面對(duì)大量并發(fā)查詢時(shí)，效果并不太理想。
　　 本文是針對(duì)道路網(wǎng)環(huán)境下的移動(dòng)對(duì)象連續(xù)七近鄰查詢處理技術(shù)展開的研究，目的在于盡可能地提高服務(wù)器端的查詢處理效率，從而縮短查詢響應(yīng)時(shí)間。所做的工作主要體現(xiàn)在以下幾個(gè)方面:
　　 (1)深入剖析了已有的基于歐式空間的和道路網(wǎng)環(huán)境下的移動(dòng)對(duì)象連續(xù)k近鄰查詢處理的經(jīng)典算法，對(duì)其一般性技術(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è)計(jì)了一種共享計(jì)算的初始結(jié)果計(jì)算算法，在查詢處理中，充分復(fù)用其他查詢的計(jì)算成果，從而避免了對(duì)道路網(wǎng)的冗余搜索。實(shí)驗(yàn)驗(yàn)證了該算法在查詢密集型道路網(wǎng)中的高效性。
　　 (3)面向高度動(dòng)態(tài)的道路網(wǎng)環(huán)境，提出了一種基于擴(kuò)展樹的連續(xù)k近鄰查詢處理方法(TL-CkNN)