受限空間環(huán)境下的移動(dòng)k近鄰查詢處理技術(shù)研究.pdf

1、隨著移動(dòng)定位技術(shù)以及空間索引技術(shù)的不斷發(fā)展，基于位置的服務(wù)也在越來越廣泛的領(lǐng)域內(nèi)得到了應(yīng)用，例如在戶外運(yùn)動(dòng)、旅游、物流運(yùn)輸甚至電子游戲等方面。基于位置服務(wù)的快速發(fā)展未來必然對(duì)人們的生產(chǎn)生活帶來巨大的變革。如何響應(yīng)移動(dòng)中的用戶對(duì)自己附近信息的查詢，是基于位置服務(wù)領(lǐng)域的基礎(chǔ)服務(wù)之一。如何高效、準(zhǔn)確地處理這種查詢，是決定基于位置服務(wù)應(yīng)用前景的關(guān)鍵問題，得到了學(xué)術(shù)界和產(chǎn)業(yè)界的廣泛關(guān)注。用戶對(duì)于自身位置信息的獲取可以通過GPS、移動(dòng)網(wǎng)絡(luò)定位、RF

2、ID標(biāo)簽等不同的方式獲得。用戶感興趣的目標(biāo)對(duì)象則以空間數(shù)據(jù)的形式存儲(chǔ)在數(shù)據(jù)庫(kù)中。針對(duì)不同的查詢類型，可以通過事先預(yù)處理的方式對(duì)數(shù)據(jù)庫(kù)里的數(shù)據(jù)事先進(jìn)行索引，以提高對(duì)應(yīng)類型查詢的處理速度。然而，查詢類型多種多樣、目標(biāo)對(duì)象所處空間也各不相同，如何針對(duì)各種受限空間中不同種類的查詢進(jìn)行建模、預(yù)處理及實(shí)時(shí)處理，是目前基于位置服務(wù)領(lǐng)域中亟待解決的熱點(diǎn)問題。移動(dòng)k近鄰查詢作為基于位置服務(wù)中的一種基礎(chǔ)查詢，更有必要進(jìn)行深入的研究。
　　本文對(duì)各種受

3、限空間中的特點(diǎn)和性質(zhì)進(jìn)行了歸納和總結(jié)，并對(duì)受限空間中移動(dòng)k近鄰的研究現(xiàn)狀進(jìn)行了分析和綜述。我們針對(duì)多種不同類型的受限空間提出了相應(yīng)的解決方案。在數(shù)據(jù)預(yù)處理、實(shí)時(shí)查詢處理等方法提出了新的模型和解決方法，建立了一套有特色的處理框架。這些技術(shù)可以有效地提高移動(dòng)k近鄰的實(shí)時(shí)處理效率和準(zhǔn)確度，從而支持受限空間中的移動(dòng)k近鄰查詢應(yīng)用。
　　具體的，本文對(duì)多種不同類型的受限空間中的移動(dòng)k近鄰查詢進(jìn)行了深入研究。這些空間包括障礙空間、存在不確定對(duì)

4、象的障礙空間、權(quán)重空間等。同時(shí)，在對(duì)象點(diǎn)移動(dòng)k近鄰的研究基礎(chǔ)上，將研究?jī)?nèi)容擴(kuò)展到移動(dòng)中路徑近鄰查詢。本文的主要內(nèi)容包括以下幾個(gè)方面:
　　(1)研究了障礙空間移動(dòng)k近鄰查詢。對(duì)移動(dòng)中進(jìn)行k近鄰查詢的特點(diǎn)進(jìn)行了分析，提出了一種有效地計(jì)算移動(dòng)查詢點(diǎn)的安全區(qū)域的方法，并將其擴(kuò)展到障礙空間中。在對(duì)障礙空間的特點(diǎn)進(jìn)行研究的基礎(chǔ)上，提出并證明了幾個(gè)關(guān)于障礙空間中安全區(qū)域的實(shí)用性質(zhì)。不同于之前的只能處理理想歐氏空間的查詢，該方法可以高效地處理障

5、礙空間的移動(dòng)查詢問題。
　　(2)研究了存在不確定對(duì)象的障礙空間移動(dòng)k近鄰查詢。在存在障礙的空間中對(duì)不確定對(duì)象移動(dòng)最近鄰查詢的處理方法進(jìn)行了研究。建立了空間障礙物及不確定對(duì)象的理論數(shù)據(jù)模型，提出障礙空間中不確定對(duì)象最近鄰查詢問題。在運(yùn)用了一種剪枝技術(shù)來提高性能的基礎(chǔ)上，設(shè)計(jì)了一種高效的基于不確定空間距離的算法來進(jìn)行查詢處理。基于不確定對(duì)象分割區(qū)域設(shè)計(jì)出一種有效的安全區(qū)域生成方法。
　　(3)研究了權(quán)重空間移動(dòng)k近鄰查詢。討論

6、權(quán)重空間中討論了MkNN問題的獨(dú)特性質(zhì)。基于聯(lián)接區(qū)域的概念，設(shè)計(jì)了一種高效的名為Weighted Indexing Map(WIM)的數(shù)據(jù)索引結(jié)構(gòu)，以大量減少需要實(shí)時(shí)MkNN處理的時(shí)間。還設(shè)計(jì)了一種名為wNeighbors的基于WIM的WkNN查詢算法。
　　(4)研究了移動(dòng)中對(duì)象路徑近鄰查詢的處理方法。對(duì)不同受限空間中的距離函數(shù)根據(jù)各種空間形式的不同特點(diǎn)進(jìn)行了抽象。研究了一種基于高效剪枝技術(shù)的可以應(yīng)用抽象距離函數(shù)的算法。以對(duì)象路