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

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

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

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

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

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

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