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

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

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

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

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

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

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

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

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