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

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

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

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

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

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

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

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

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