基于Voronoi圖的路網(wǎng)中的概率最近鄰和排序反向k近鄰查詢研究.pdf

1、隨著無線通信技術的發(fā)展和智能終端的不斷普及，基于位置的服務（Location-Based Services:LBS）迎來了新的發(fā)展契機，LBS市場呈現(xiàn)爆發(fā)式增長。作為LBS的核心技術之一，位置相關查詢也隨之成為學術界和工業(yè)界共同關注的熱點問題。在眾多的位置相關查詢中，最近鄰查詢和反向最近鄰查詢被認為是最基礎和應用最廣泛的查詢類型。最近鄰查詢既可以單獨作為LBS服務來提供，比如查找最近的餐館、酒店等，也可以作為基礎技術為其他查詢（如反向最

2、近鄰查詢、窗口查詢等）提供支持。反向最近鄰查詢在涉及到一個對象對其他對象的“影響范圍”和“影響程度”時有很好的應用，比如在新建商場、醫(yī)院等基礎設施時的選址問題和現(xiàn)在很熱門的針對性廣告（targeted advertising）。
　　現(xiàn)代社會路網(wǎng)（公路、鐵路等）發(fā)達，人們的很多活動都發(fā)生在路網(wǎng)空間，比如導航、旅行等。同時，路網(wǎng)的發(fā)達也使得歐氏距離不再適用于估計對象間的距離，尤其是在路網(wǎng)密集的城市地區(qū)。因此，研究適用于路網(wǎng)的最近鄰查

3、詢算法很有必要。另外，由于定位不精準、傳輸帶寬限制、隱私保護等原因，不確定性在LBS中廣泛存在。而簡單的用點數(shù)據(jù)來代表位置不確定對象的做法通常會導致查詢結(jié)果不夠準確甚至出錯。因此，很有必要研究路網(wǎng)中的基于位置不確定對象的最近鄰查詢。
　　Voronoi圖由于天然保存了最近鄰信息，因此常常被用于處理最近鄰和反向最近鄰查詢。雖然已有算法可以計算歐氏空間中基于不確定對象的Voronoi圖和路網(wǎng)中基于確定對象的Voronoi圖，但還沒有算

4、法用于構造路網(wǎng)空間中基于不確定對象的Voronoi圖（Network Uncertain Voronoi Diagram:UNVD）。為了更深入、系統(tǒng)地研究UNVD，文中按照所劃分空間的不同將UNVD分成node-UNVD、link-UNVD和area-UNVD三種類型，分別對應路網(wǎng)節(jié)點空間、路網(wǎng)邊空間和由路網(wǎng)及路網(wǎng)所在平面構成的組合空間。并且，針對每一種類型的UNVD，首次提出了構造方法。算法MarkV用來構造node-UNVD，通過

5、對每個路網(wǎng)節(jié)點賦予標簽來記錄當前的可能最近對象及其與路網(wǎng)節(jié)點間的距離范圍，只需遍歷一次路網(wǎng)便可求出所有路網(wǎng)節(jié)點的可能最近對象集合。相比基于最短路徑的直觀算法，MarkV可以減少80％的時間開銷。在node-UNVD的基礎上，對路網(wǎng)邊進一步劃分，使得每條子邊上的點的可能最近對象相同，便得到link-UNVD。以link-UNVD中的Voronoi單元為生成對象來構造歐氏空間的線段Voronoi圖即得到area-UNVD。
　　本文首

6、次給出路網(wǎng)空間中的概率最近鄰（Network Probabilistic Nearest Neighbor:NPNN）查詢處理方法。該方法利用預計算的link-UNVD來處理NPNN查詢。首先，給出了公式用于計算結(jié)果對象成為最近鄰的概率。然后，提出了四叉樹結(jié)構的索引gIndex和哈希表索引qIndex來對link-UNVD的邊、邊的可能最近對象和該對象成為最近鄰的概率進行索引。最后，基于提出的索引結(jié)構，分別給出了快照和連續(xù)的NPNN查詢

7、處理方法。實驗結(jié)果顯示，gIndex和qIndex在NPNN查詢過程中的I/O性能和時間性能均優(yōu)于其他索引技術。
　　對于反向最近鄰，介紹了一種新的查詢類型，排序反向最近鄰（Ordered Reverse k Nearest Neighbor:ORkNN）查詢。與普通的反向最近鄰相比，ORkNN查詢的內(nèi)容額外包括了“影響程度大小”信息，因此，利用ORkNN查詢能夠提供更加精準和人性化的服務。為了適應移動計算環(huán)境的需要，研究了在按需

8、廣播的環(huán)境中處理ORkNN查詢的方法。該方法利用了高階排序Voronoi圖來處理ORkNN查詢。通常情況下，預處理的Voronoi圖不適合用來處理高階反向最近鄰查詢，因為在k值提前不知道的情況下，需要預計算多個Voronoi圖來應對k值不斷變化的查詢請求，從而造成極大的計算開銷。該研究通過進一步開發(fā)高階排序Voronoi圖的性質(zhì)，做到只需要預計算一個高階排序Voronoi圖即可處理所有的ORkNN查詢請求，大大減少了預計算的開銷。另外，