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

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

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

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

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

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

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