路網(wǎng)上的單色和雙色反k最遠(yuǎn)鄰查詢(xún)

王寶文，彭 川，陳子軍，劉文遠(yuǎn)

（1.燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島066004；2.河北省計(jì)算機(jī)虛擬技術(shù)與系統(tǒng)集成重點(diǎn)實(shí)驗(yàn)室，河北秦皇島066004）

0 引 言

近年來(lái)空間數(shù)據(jù)庫(kù)的研究備受人們關(guān)注，已成為一個(gè)熱點(diǎn)研究領(lǐng)域。反最遠(yuǎn)鄰查詢(xún)是空間數(shù)據(jù)庫(kù)理論與應(yīng)用中的一類(lèi)新問(wèn)題。所謂反最遠(yuǎn)鄰查詢(xún)就是找到以給定的查詢(xún)點(diǎn)作為其最遠(yuǎn)鄰的目標(biāo)點(diǎn)。它主要是解決根據(jù)給定點(diǎn)找到那些具有最小影響的點(diǎn)。而反最遠(yuǎn)鄰查詢(xún)的研究工作主要是在歐式空間下進(jìn)行的，本文則是研究路網(wǎng)上的反k最遠(yuǎn)鄰的查詢(xún)問(wèn)題。完善了反最遠(yuǎn)鄰查詢(xún)技術(shù)。

反最遠(yuǎn)鄰查詢(xún)的應(yīng)用十分廣泛。文獻(xiàn) ［1］給出了幾個(gè)在歐式空間下反最遠(yuǎn)鄰在現(xiàn)實(shí)生活中的應(yīng)用。如化學(xué)工廠(chǎng)選址、避免同業(yè)競(jìng)爭(zhēng)等問(wèn)題。然而，在路網(wǎng)的環(huán)境下，反最遠(yuǎn)鄰也有著其重要的應(yīng)用價(jià)值。比如，在我們的日常生活中，消費(fèi)者都喜歡到離他家近的商場(chǎng)去購(gòu)買(mǎi)商品。除非有特殊原因，一般他們都不會(huì)去那些離他家很遠(yuǎn)的商場(chǎng)購(gòu)物，即使那個(gè)商場(chǎng)的規(guī)模很大，商品很全，優(yōu)惠或者活動(dòng)很多。但那些大型商場(chǎng)的經(jīng)營(yíng)者肯定希望盡可能多的消費(fèi)者去他們的商場(chǎng)購(gòu)物。所以他們就要查找出哪些消費(fèi)者離商場(chǎng)最遠(yuǎn)，最不可能到他們的商場(chǎng)來(lái)購(gòu)物。找到這樣的消費(fèi)群體以后，采取一些有效的市場(chǎng)營(yíng)銷(xiāo)策略。比如在他們住的地方加大廣告宣傳力度，或者開(kāi)通他們住的地方直達(dá)商場(chǎng)的購(gòu)物班車(chē)等等。

在現(xiàn)實(shí)生活中，在路網(wǎng)環(huán)境下研究反最遠(yuǎn)鄰則更接近我們的日常生活，本文就是將歐式空間的反最遠(yuǎn)鄰擴(kuò)展到了路網(wǎng)上，提出了在路網(wǎng)環(huán)境下的單色反k最遠(yuǎn)鄰（MRkFN）和雙色反k最遠(yuǎn)鄰 （BRkFN）的定義和查詢(xún)算法。經(jīng)驗(yàn)證，反最遠(yuǎn)鄰有著很重要的研究?jī)r(jià)值和重要意義。

1 相關(guān)工作

自從美國(guó)AT＆T實(shí)驗(yàn)室的Flip Korn和 Muthukrishnan.S［2］第一次提出反最近鄰查詢(xún)以來(lái)，數(shù)據(jù)庫(kù)界對(duì)它給予了極大的關(guān)注。反最近鄰查詢(xún)目的是發(fā)現(xiàn)影響集，它的應(yīng)用十分廣泛，如決策支持系統(tǒng)、市場(chǎng)決策、資料庫(kù)文件搜索、生物資訊、基于位置的服務(wù)、資源分配等方面都有著重要的應(yīng)用價(jià)值。直至現(xiàn)在不管是在歐式空間下，還是在路網(wǎng)的環(huán)境下，都提出了很多有效的解決反最近鄰查詢(xún)的方法：基于預(yù)計(jì)算的方法、不需要預(yù)計(jì)算所有最近鄰的60°裁剪法、完全不需要預(yù)計(jì)算的TPL裁剪策略等。另外，文獻(xiàn) ［3－7］提出了各種反k最近鄰查詢(xún)的解決方法，解決了單色和雙色反k最近鄰查詢(xún)問(wèn)題，連續(xù)反k最近鄰查詢(xún)問(wèn)題等。Y.Tao等［8］人解決了在路網(wǎng)中的反最近鄰問(wèn)題。

而相對(duì)于反最近鄰來(lái)說(shuō)，反最遠(yuǎn)鄰則是最近幾年才逐漸成為研究的熱點(diǎn)。它是在反最近鄰查詢(xún)的基礎(chǔ)上提出的一個(gè)相對(duì)的概念。2009年李博涵，郝忠孝等人［9］提出了在明氏空間下利用離散邊界點(diǎn)及鄰域區(qū)等概念得到用于判定RFN的候選集的相關(guān)性質(zhì)和定理，并給出其過(guò)濾算法。在得到過(guò)濾的候選集基礎(chǔ)上，提出了F－RFN查詢(xún)算法。2009年Bin Yao等人［1］提出了在歐式空間下的單色和雙色反最遠(yuǎn)鄰查詢(xún)，并提出了一種新的查詢(xún)算法，即采用了最遠(yuǎn)單元 （PFC）算法和凸包最遠(yuǎn)單元算法 （CHFC）來(lái)進(jìn)行反最遠(yuǎn)鄰的查詢(xún)。這兩種算法都采用了R－tree索引結(jié)構(gòu)和使用了最遠(yuǎn)Vorionoi圖來(lái)判斷對(duì)象點(diǎn)是否是查詢(xún)點(diǎn)的反最遠(yuǎn)鄰。2010年Jianquan Liu等人［10］在Bin Yao提出的反最遠(yuǎn)鄰查詢(xún)算法基礎(chǔ)上進(jìn)行了改進(jìn)和優(yōu)化，提出了一種新的優(yōu)化算法，有效地提高了查詢(xún)效率，縮短了查詢(xún)時(shí)間。在2009年Quoc Thai Tran等人［11］首次提出了路網(wǎng)上的反最遠(yuǎn)鄰查詢(xún)，他們主要是利用網(wǎng)絡(luò)Vorionoi圖和Dijkstra算法來(lái)查詢(xún)路網(wǎng)上的單色反k最遠(yuǎn)鄰，這種算法需要大量的預(yù)計(jì)算，而且查詢(xún)效率也不高。然而本文提出的算法不僅不需要預(yù)計(jì)算，而且查詢(xún)效率也有了很大的提高。

Quoc Thai Tran等人雖然首次提出了路網(wǎng)上的反最遠(yuǎn)鄰查詢(xún)，但他們并沒(méi)有解決基于路網(wǎng)的雙色反k最遠(yuǎn)鄰查詢(xún)問(wèn)題。因?yàn)樗麄儾捎昧薞orionoi圖的思想來(lái)處理反最遠(yuǎn)鄰查詢(xún)問(wèn)題，而使用Vorionoi圖查找雙色反最遠(yuǎn)鄰時(shí)預(yù)計(jì)算占用的內(nèi)存資源非常大。因此，文本采用轉(zhuǎn)化的思想把反最遠(yuǎn)鄰查詢(xún)轉(zhuǎn)化為反最近鄰查詢(xún)問(wèn)題，利用反最近鄰的查詢(xún)方法解決反最遠(yuǎn)鄰查詢(xún)問(wèn)題。

2 問(wèn)題定義及性質(zhì)

2.1 問(wèn)題定義

在本文中，假設(shè)G（V，E）是帶權(quán)的無(wú)向連通圖，其中路網(wǎng)中的頂點(diǎn)的集合是V，邊的集合是E，而在邊集合E中，e為其中的一條邊。頂點(diǎn)集合V中的個(gè)數(shù)為n。路網(wǎng)中對(duì)象點(diǎn)既有可能在路網(wǎng)的邊上，也有可能在路網(wǎng)的頂點(diǎn)上。如果對(duì)象點(diǎn)在路網(wǎng)的邊上，則需要做一個(gè)變化，把該邊變成兩條邊，讓對(duì)象點(diǎn)成為一個(gè)路網(wǎng)上的頂點(diǎn)。例如，p是路網(wǎng)上的一個(gè)在邊 （u，v）上的對(duì)象點(diǎn)，則用 （u，p）和（p，v）替換 （u，v）。把p看成頂點(diǎn)加入V中。下面給出了相關(guān)的定義。

本文用dist（p，q）表示任意兩個(gè)點(diǎn)之間的路網(wǎng)距離。

定義1 最短路徑 （shortestPath）：已知帶權(quán)無(wú)向連通圖G （V，E），兩個(gè)對(duì)象點(diǎn)p1和p2是路網(wǎng)G （V，E）的兩個(gè)不同的頂點(diǎn)。p1和p2在路網(wǎng)上的最短路徑就是p1與p2之間所有路徑中路網(wǎng)距離最小的那條路徑。

定義2 最遠(yuǎn)鄰查詢(xún) （FN）：假設(shè)一個(gè)數(shù)據(jù)集P＝｛p1，p2，p3...，pn｝和一個(gè)查詢(xún)點(diǎn)q，F(xiàn)N查詢(xún)就是要找出P的子集FN （q），滿(mǎn)足：FN （q）＝ ｛p∈P｜p′∈P：dist（p，q）≥dist（p′，q）｝。

定義3 k最遠(yuǎn)鄰查詢(xún) （kFN）：假設(shè)一個(gè)數(shù)據(jù)集P和一個(gè)查詢(xún)點(diǎn)q，kFN （q）是查詢(xún)點(diǎn)q的k最遠(yuǎn)鄰結(jié)果集，假設(shè)p∈kFN （q），則必須滿(mǎn)足下面的條件

｜｛o∈P｜dist（o，q）＞dist（p，q）｝｜＜k

定義4 反最遠(yuǎn)鄰查詢(xún) （RFN）：RFN與RNN的定義類(lèi)似，給定一個(gè)數(shù)據(jù)集P和一個(gè)查詢(xún)點(diǎn)q，RFN就是要找出P的子集RFN （q），滿(mǎn)足：RFN （q）＝ ｛p｜p∈P且q∈FN （p）｝。

定義5 單色反k最遠(yuǎn)鄰 （MRkFN）：?jiǎn)紊磌最遠(yuǎn)鄰查詢(xún)就是查詢(xún)點(diǎn)q與對(duì)象點(diǎn)p是相同的數(shù)據(jù)類(lèi)型，找出數(shù)據(jù)集P的子集MRkFN （q），滿(mǎn)足：MRkFN （q）＝ ｛p∈P｜q∈kFN （p）｝。

圖1 單色反k最遠(yuǎn)鄰 （MRkFN）

圖1是一個(gè)單色反k最遠(yuǎn)鄰的示例。給定數(shù)據(jù)集P＝｛p1，p2，p3…，p8｝和查詢(xún)點(diǎn)q，且q和P中的點(diǎn)屬于同一種類(lèi)型。圖1中有8個(gè)對(duì)象點(diǎn)，顯然的2FN （q）＝｛p4，p8｝。然而，p8卻不是q的單色反2最遠(yuǎn)鄰，因?yàn)?FN （p8）＝ ｛p1，p2｝，所以，由定義5可知p8不是q的單色反2最遠(yuǎn)鄰，而p1是q的單色反2最遠(yuǎn)鄰，這是因?yàn)閝∈2FN （p1）。這就說(shuō)明了對(duì)象點(diǎn)p是查詢(xún)點(diǎn)q的最遠(yuǎn)鄰，但并不一定是q的反最遠(yuǎn)鄰，反之亦然。根據(jù)定義4進(jìn)一步判斷可知，q的單色反2最遠(yuǎn)鄰MR2FN（q）＝ ｛p1，p2，p3，p4｝。

定義6 雙色反k最遠(yuǎn)鄰 （BRkFN）：假設(shè)q∈Q，p∈P，Q和P是兩種不同的數(shù)據(jù)類(lèi)型。雙色反k最遠(yuǎn)鄰查詢(xún)就是要找到數(shù)據(jù)集P的子集BRkFN （q），滿(mǎn)足：BRkFN （q）＝ ｛p∈P｜q∈BkFN （p）｝。

圖2 雙色反k最遠(yuǎn)鄰 （BRkFN）

圖2是一個(gè)雙色反k最遠(yuǎn)鄰的示例。給定對(duì)象點(diǎn)集合P＝｛p1，p2，p3…，p6｝和查詢(xún)點(diǎn)集合Q＝｛q1，q2，q3…，q6｝。由定義6可知，q1的雙色反2最遠(yuǎn)鄰BR2FN （q1）＝｛p6｝，因?yàn)閜6的2最遠(yuǎn)鄰2FN＝｛q1，q2｝，包含了q1。而q5的雙色反2最遠(yuǎn)鄰為空，因?yàn)閷?duì)任意的pi∈P（1≤i≤6），

定義7 標(biāo)記點(diǎn)［12］：所謂標(biāo)記點(diǎn)就是假設(shè)G （V，E）是一個(gè)路網(wǎng)，q和p分別是路網(wǎng)上的查詢(xún)點(diǎn)和對(duì)象點(diǎn)。而u是p和q之間的最短路徑上的一點(diǎn)，若dist（u，p）＝dist（u，q），則u就稱(chēng)為標(biāo)記p和q之間的標(biāo)記點(diǎn)。標(biāo)記點(diǎn)既可能在路網(wǎng)的邊上，也可能在頂點(diǎn)上。

在本文中，若對(duì)象點(diǎn)和查詢(xún)點(diǎn)之間存在多條最短路徑，本文提出的算法會(huì)隨機(jī)選擇一條。因此也只能得到一個(gè)標(biāo)記點(diǎn)。而且，位置相同的標(biāo)記點(diǎn)在本文中會(huì)被認(rèn)為是兩個(gè)標(biāo)記點(diǎn)。為了確保本文提出的算法的正確性，落在頂點(diǎn)上的標(biāo)記點(diǎn)不計(jì)數(shù)。

2.2 問(wèn)題性質(zhì)

本文提出的算法的思想是把反最遠(yuǎn)鄰查詢(xún)問(wèn)題轉(zhuǎn)化為反最近鄰查詢(xún)問(wèn)題。然后利用一些反最近鄰的查詢(xún)方法來(lái)處理反最遠(yuǎn)鄰查詢(xún)。假設(shè)數(shù)據(jù)集P＝ ｛p1，p2，p3…，pn｝和查詢(xún)點(diǎn)q，要查找查詢(xún)點(diǎn)q的反最遠(yuǎn)鄰，換個(gè)角度思考就是要排除掉查詢(xún)點(diǎn)q的相應(yīng)的反最近鄰。因此，通過(guò)這一轉(zhuǎn)換，很多反最近鄰的查詢(xún)算法的研究成果就可以應(yīng)用在反最遠(yuǎn)鄰的研究中。根據(jù)這一轉(zhuǎn)換思想，下面給出了兩個(gè)定理：

定理1 如果p是q的單色反k最遠(yuǎn)鄰，那么p一定不是q的單色反n－k－1最近鄰。其中n是所有的興趣點(diǎn)的個(gè)數(shù)。可形式化表示為：P＝ ｛p1，p2，…，pn｝，pi∈P，（1≤i≤n），q∈P

證明：

假設(shè)p∈MRkFN （q），對(duì)任意的p∈MRkFN （q），p是q的第i個(gè)反最遠(yuǎn)鄰 （1≤i≤k）。由定義5可知，p的k最遠(yuǎn)鄰包含q。因?yàn)閝屬于p的k最遠(yuǎn)鄰，所以q肯定不是p的n－k－1最近鄰。那么，

如圖1所示，圖1中有8個(gè)對(duì)象點(diǎn)和1個(gè)查詢(xún)點(diǎn)，則總共有9個(gè)興趣點(diǎn)。利用定理1找出查詢(xún)點(diǎn)q的單色反2最遠(yuǎn)鄰，即排除那些是q的單色反 （9－2－1）最近鄰。進(jìn)一步分析就是要找出哪些對(duì)象點(diǎn)的6最近鄰不包含q，則這樣的對(duì)象點(diǎn)就是我們要找的q的反2最遠(yuǎn)鄰。圖1中，p1的6最近鄰6NN （p1）＝ ｛p2，p3，p4，p5，p6，p7｝，（p1）。所以，p1是q的MR2FN。同理，可找出q的單色反2最遠(yuǎn)鄰結(jié)果集為 MR2FN （q）＝ ｛p1，p2，p3，p4｝。

定理2 假設(shè)P和Q是兩種不同類(lèi)型的點(diǎn)集，如果p是q的雙色反k最遠(yuǎn)鄰，且p∈P和q∈Q，那么p一定不是q的雙色反n－k最近鄰。其中n是Q中點(diǎn)的個(gè)數(shù)。即

定理2的證明與定理1的證明類(lèi)似。不同之處在于在轉(zhuǎn)化的時(shí)候，單色反k最遠(yuǎn)鄰是要排除查詢(xún)點(diǎn)的單色反nk－1最近鄰，而雙色反k最遠(yuǎn)鄰是要排除查詢(xún)點(diǎn)的雙色反nk最近鄰。這是因?yàn)閱紊醋罱彶樵?xún)時(shí)，查詢(xún)點(diǎn)和對(duì)象點(diǎn)都屬于同一種數(shù)據(jù)類(lèi)型，考慮了查詢(xún)點(diǎn)本身，而雙色反最近鄰查詢(xún)沒(méi)有考慮查詢(xún)點(diǎn)本身，因?yàn)殡p色反最近鄰查詢(xún)查詢(xún)點(diǎn)和對(duì)象點(diǎn)分別屬于兩種不同的數(shù)據(jù)類(lèi)型。

如圖2所示，圖2中有兩種類(lèi)型的興趣點(diǎn)，分別為P型點(diǎn)和Q型點(diǎn)。其中Q型點(diǎn)的個(gè)數(shù)為6。利用定理2找出查詢(xún)點(diǎn)q1的雙色反2最遠(yuǎn)鄰。即排除那些是q1點(diǎn)的反 （6－2）最近鄰的點(diǎn)。就是要找出哪些P型點(diǎn)的4最近鄰的結(jié)果集里不包含查詢(xún)點(diǎn)q1，則這樣的點(diǎn)就是我們要找的q1的雙色反2最遠(yuǎn)鄰。圖2中，p1的4最近鄰4NN （p1）＝ ｛q1，q2，q3，q5｝。因?yàn)閝1∈4NN （p1），所以由定理2可知p1不是q1的雙色反2最遠(yuǎn)鄰。而4NN （p6）＝ ｛q3，q4，q5，q6｝，q1不在p6的4最近鄰的結(jié)果集中。所以p6∈BR2FN （q1）。最后，可求出BR2FN （q1）＝ ｛p6｝。由定理1、定理2可知，它們對(duì)歐式空間和在路網(wǎng)的環(huán)境下也都適用。

3 相關(guān)算法

3.1 路網(wǎng)上單色反k最遠(yuǎn)鄰查詢(xún)算法

本算法采用了定理1和標(biāo)記點(diǎn)的思想，所謂標(biāo)記點(diǎn)的思想［12］就是假設(shè)在查詢(xún)點(diǎn)q和數(shù)據(jù)對(duì)象點(diǎn)p之間的最短路徑邊上總共有i個(gè)標(biāo)記點(diǎn)，且i＞k，則p一定不是q的反k最近鄰。

算法中首先找出路網(wǎng)上所有對(duì)象點(diǎn)和查詢(xún)點(diǎn)之間的最短路徑，然后在最短路徑上找到標(biāo)記點(diǎn)。最后根據(jù)落在對(duì)象點(diǎn)與查詢(xún)點(diǎn)最短路徑上的標(biāo)記點(diǎn)的個(gè)數(shù)直接找到反k最遠(yuǎn)鄰。具體算法如下：

算法1MRkFN算法／／求出給定查詢(xún)點(diǎn)的單色反k最遠(yuǎn)鄰

輸入：路網(wǎng)G （V，E），查詢(xún)點(diǎn)q，反最遠(yuǎn)鄰數(shù)k

輸出：查詢(xún)點(diǎn)q的結(jié)果集Sr

算法1就是查找查詢(xún)點(diǎn)q的單色反k最遠(yuǎn)鄰。Sr是找到的反k最遠(yuǎn)鄰的結(jié)果集。其中第3行利用了定理1中的轉(zhuǎn)化思想，把反k最遠(yuǎn)鄰查詢(xún)轉(zhuǎn)化為反n－k－1最近鄰查詢(xún)。然后再利用標(biāo)記點(diǎn)的思想來(lái)查找反n－k－1最近鄰。其中4行就是根據(jù)標(biāo)記點(diǎn)的定義，利用Dijkstra算法求出了查詢(xún)點(diǎn)與所有對(duì)象點(diǎn)之間的標(biāo)記點(diǎn)。5－10行則是利用求出的標(biāo)記點(diǎn)的個(gè)數(shù)直接找到查詢(xún)點(diǎn)的反k最遠(yuǎn)鄰。如果標(biāo)記點(diǎn)的總個(gè)數(shù)大于k1，則直接把該對(duì)象點(diǎn)放入Sr中，否則放入Sc中有待進(jìn)一步驗(yàn)證。11－13行就是驗(yàn)證Sc中的點(diǎn)是否是查詢(xún)點(diǎn)的反k最遠(yuǎn)鄰。

圖3 單色反2最遠(yuǎn)鄰示例

如圖3所示，圖3中有8個(gè)興趣點(diǎn)，且都屬于同一類(lèi)型。令q為查詢(xún)點(diǎn)，k＝2，則k1＝8－2－1＝5。首先利用Dijkstra算法找出查詢(xún)點(diǎn)q與對(duì)象點(diǎn)之間的標(biāo)記點(diǎn)mp1～mp7。然后計(jì)算各個(gè)對(duì)象點(diǎn)到查詢(xún)點(diǎn)的最短路徑上的標(biāo)記點(diǎn)的總個(gè)數(shù)。p1，p2的marktotal為3，p3，p4的marktotal為4。只有p5，p6，p7的 marktotal為6大于5，則直接把p5，p6，p7放入Sr中，而把p1，p2，p3，p4放入Sc中需要進(jìn)一步驗(yàn)證。經(jīng)過(guò)進(jìn)一步驗(yàn)證p1，p2，p3，p4不是q的反2最遠(yuǎn)鄰。所以查詢(xún)點(diǎn)q的單色反2最遠(yuǎn)鄰最終結(jié)果為 ｛p5，p6，p7｝。

MRkFN算法的時(shí)間復(fù)雜度分析：假設(shè)n是路網(wǎng)中的頂點(diǎn)數(shù)，e是路網(wǎng)中邊的條數(shù)。則Dijkstra算法的時(shí)間復(fù)雜度為O （（n＋e）logn）。MRkFN中第4行的時(shí)間復(fù)雜度為O（（n＋e）logn）。5－10行的時(shí)間復(fù)雜度是 O （n）。11－13行的時(shí)間復(fù)雜度是O （n（n＋e）logn），因?yàn)楹蜻x集Sc中的對(duì)象個(gè)數(shù)最多為n個(gè)。故算法1的時(shí)間復(fù)雜度是O （n（n＋e）logn）。

3.2 路網(wǎng)上雙色反k最遠(yuǎn)鄰查詢(xún)算法

假設(shè)有兩種不同類(lèi)型的數(shù)據(jù)集Q和P，查詢(xún)點(diǎn)q（Q。n為Q中所有點(diǎn)的個(gè)數(shù)。雙色反k最遠(yuǎn)鄰查詢(xún)就是要找出在數(shù)據(jù)集P中以查詢(xún)點(diǎn)q為它的最遠(yuǎn)鄰的對(duì)象點(diǎn)的集合。雙色反k最遠(yuǎn)鄰查詢(xún)算法跟單色反k最遠(yuǎn)鄰查詢(xún)算法有很多相似之處，不同之處是單色反k最遠(yuǎn)鄰查詢(xún)算法中k1的值為n－k－1（n是興趣點(diǎn)的個(gè)數(shù)），而雙色反k最遠(yuǎn)鄰查詢(xún)算法中的k1的值為n－k（其中n為Q中所有點(diǎn)的個(gè)數(shù)）。在用Dijkstra算法求最短路徑的時(shí)候，雙色反k最遠(yuǎn)鄰查詢(xún)算法不再是求查詢(xún)點(diǎn)q與P中的對(duì)象點(diǎn)的最短路徑，而是求查詢(xún)點(diǎn)q與Q中其他點(diǎn)之間的最短路徑，并做出標(biāo)記點(diǎn)。

圖4 雙色反6最遠(yuǎn)鄰示例

如圖4所示，給出了一個(gè)雙色反6最遠(yuǎn)鄰的示例。圖4中黑色的點(diǎn)表示Q類(lèi)型的點(diǎn)，總共有10個(gè)。令q為查詢(xún)點(diǎn)，k＝6，則k1＝n－k＝10－6＝4。先用Dijkstra算法分別找到查詢(xún)點(diǎn)q與點(diǎn)q1～q9之間的最短路徑，并在其最短路徑上做上標(biāo)記點(diǎn)mq1～ mq9。其中點(diǎn)q6到q的最短路徑有兩條，分別是 ｛q6，p7，q4，p4，q｝， ｛q6，q5，p4，q｝。遇到此類(lèi)情況，算法會(huì)隨機(jī)地選擇一條最短路徑來(lái)處理。在本例中算法選取 ｛q6，q5，p4，q｝作為q6到q的最短路徑。然后分別求出q點(diǎn)到p1～p12的最短路徑上的所有頂點(diǎn)的 markcount之和 marktotal。其中 p8，p9，p11，p12的marktotal都為5，即大于k1，所以直接把p8，p9，p11，p12放入Sr。把剩余的對(duì)象點(diǎn)放入Sc中，即Sc＝ ｛p1，p2，p3，p4，p5，p6，p7，p10｝。然后對(duì)Sc中的候選點(diǎn)進(jìn)行驗(yàn)證。因?yàn)?B4NN （p3）＝ ｛q1，q2，q3，q4｝，q不 屬 于B4NN （p3），所以p3也是q的反6最遠(yuǎn)鄰。最后驗(yàn)證結(jié)果Sr為 ｛p3，p8，p9，p11，p12｝。

4 實(shí)驗(yàn)結(jié)果與分析

本節(jié)將測(cè)試本文所提出了MRkFN和BRkFN兩種查詢(xún)算法的性能和效率。測(cè)試中使用了加利福尼亞的路網(wǎng)數(shù)據(jù)和 building 類(lèi) 型 的 數(shù) 據(jù) 點(diǎn) 集 （http：／／www.cs.fsu.edu／lifeifei／SpatialDataset.htm），其中加利福尼亞的路網(wǎng)數(shù)據(jù)中共包含21048個(gè)頂點(diǎn)和21693條邊。｜building｜＝4110。測(cè)試中采用了模擬興趣點(diǎn)的方式，隨機(jī)地選擇路網(wǎng)中某些結(jié)點(diǎn)作為查詢(xún)點(diǎn)和興趣點(diǎn)。每種算法都經(jīng)過(guò)了30次測(cè)試，然后取得平均值得到的實(shí)驗(yàn)結(jié)果。

實(shí)驗(yàn)硬件環(huán)境為AMD雙核2.21GHz的CPU，2G內(nèi)存，軟件環(huán)境使用Windows XP操作系統(tǒng)和VS2005開(kāi)發(fā)環(huán)境。算法用C＋＋實(shí)現(xiàn)。

4.1 MRkFN實(shí)驗(yàn)結(jié)果與分析

如表1所示，我們根據(jù)興趣點(diǎn)的個(gè)數(shù)把興趣點(diǎn)分成了低、中、高3種不同的密度。興趣點(diǎn)的個(gè)數(shù)小于30的是低密度，大于60的是高密度，在30和60之間的是中密度。如圖5所示為隨著k值的不斷變化，3種不同密度下的MRkFN查詢(xún)時(shí)間的變化?？梢钥闯鲭S著k值越來(lái)越大，MRkFN的查詢(xún)時(shí)間越來(lái)越少。這是因?yàn)閗值越大，則n－k－1的值就越小，就有可能有更多的對(duì)象點(diǎn)，它到查詢(xún)點(diǎn)的的最短路徑上的所有標(biāo)記點(diǎn)的個(gè)數(shù)大于n－k－1。而且，還可以看出，高密度的興趣點(diǎn)隨著k值的變化最大。本實(shí)驗(yàn)說(shuō)明本文提出的MRkFN算法適合查找興趣點(diǎn)密度大，k值大的查詢(xún)點(diǎn)的單色反k最遠(yuǎn)鄰。

表1 k＝1和k＝6的實(shí)驗(yàn)數(shù)據(jù)

表2 k＝12和k＝18的實(shí)驗(yàn)數(shù)據(jù)表

表3 k＝24的實(shí)驗(yàn)數(shù)據(jù)表

圖5 興趣點(diǎn)密度對(duì)時(shí)間的影響

4.2 BRkFN實(shí)驗(yàn)結(jié)果與分析

如圖6所示，圖6中兩條曲線(xiàn)表示的是兩種不同的BRkFN算法在不同的k值下的時(shí)間效率。樸素的BRkFN就是沒(méi)有采用標(biāo)記點(diǎn)的思想，直接用Dijkstra算法排除查詢(xún)點(diǎn)的反n－k最近鄰。可以看出隨著k值的增加，本文提出的優(yōu)化的BRkFN算法的優(yōu)化效果就越明顯。這是因?yàn)閗值越大，n－k的值就越小，則通過(guò)標(biāo)記點(diǎn)找到的反最遠(yuǎn)鄰就越多。所以，查詢(xún)時(shí)間就越少。

圖6 BRkFN兩種算法的比較

5 結(jié)束語(yǔ)

本文采用了轉(zhuǎn)換的思想，從反最近鄰的角度來(lái)思考分析和解決了反最遠(yuǎn)鄰查詢(xún)問(wèn)題，把歐式空間下的反最遠(yuǎn)鄰查詢(xún)擴(kuò)展到了路網(wǎng)上。提出了一種新的基于路網(wǎng)的單色反k最遠(yuǎn)鄰和雙色反k最遠(yuǎn)鄰查詢(xún)算法。完善了空間數(shù)據(jù)庫(kù)中查詢(xún)技術(shù)領(lǐng)域的理論研究工作。并通過(guò)實(shí)驗(yàn)驗(yàn)證了兩種算法的有效性。在今后的工作中，我們將研究在路網(wǎng)的環(huán)境下，查詢(xún)點(diǎn)是移動(dòng)的或者對(duì)象點(diǎn)是移動(dòng)的反最遠(yuǎn)鄰查詢(xún)。還有就是高維空間中的反最遠(yuǎn)鄰查詢(xún)算法的研究。

［1］YAO B，LI F，Kumar P.Reverse furthest neighbors in spatial databases ［C］.Proceedings of the IEEE International Conference on Data Engineering，2009：664－675.

［2］Korn F，Muthukrishnan S.Influence sets based on reverse nearest neighbor queries ［C］.Proceedings of the ACM SIGMOD International Conference on Management of Data，2000：201－212.

［3］James M Kang，Mohamed F Mokbel，Shashi Shekhar，et al.Continuous evaluation of monochromatic and bichromatic reverse nearest neighbors ［C］.IEEE 23rd International Conference on Data Engineering，2007：806－815.

［4］Muhammad Aamir Cheema，LIN Xuemin，ZHANG Ying，et al.Lazy updates：An efficient technique to continuously monitoring reverse kNN ［J］.Proceedings of the VLDB Endowment，2009，2 （1）：1138－1149.

［5］Mahady Hasan，Muhammad Aamir Cheema，Xuemin Lin，et al.Efficient construction of safe regions for moving kNN queries over dynamic datasets ［M］.The University of New South Wales Australia SSTD，2009：373－379.

［6］WU W，YANG F，CHAN C，et al.FINCH：Evaluating reverse k－nearest－neighbor queries on location data ［C］.Auckland，New Zealand VLDB，2008：1056－1067.

［7］WU Wei，YANG Fei，Chee Yong Chan，et al.Continuous reverse k－nearest－neighbor monitoring ［C］.9th International Conference on Mobile Data Management，2008：132－139.

［8］YIU M L，Papadias D，Mamoulis N，et al.Reverse nearest neighbors in large graphs ［J］.IEEE Transactions on Knowledge and Data Engineering，2006，18 （4），540－553.

［9］LI Bohan，HAO Zhongxiao.Efficient filtration and query algorithm of reverse furthest neighbor ［J］.Mini－Micro Systems，2009，30 （10）：1948－1951 （in Chinese）.［李博涵，郝忠孝.反向最遠(yuǎn)鄰的有效過(guò)濾和查詢(xún)算法 ［J］.小型微型計(jì)算機(jī)系統(tǒng)，2009，30 （10）：1948－1951.］

［10］LIU Jianquan，CHEN Hanxiong，Kazutaka Furuse.Hiroyuki kitagawa：An efficient algorithm for reverse furthest neighbors query with metric index ［G］.LNCS 6262：Berlin Heidelberg DEXA，2010：437－451.

［11］Quoc Thai Tran，David Taniar.Maytham safar：Reverse k nearest neighbor and reverse farthest neighbor search on spatial networks ［J］.Transactions on Large－Scale Data－and Knowledge－Centered Systems I，2009：353－372.

［12］CHEN Zijun，WANG Lu，LIU Wenyuan.Method for mutual nearest neighbor query in road networks ［J］.Mini－Micro Systems，2011，32 （4）：607－609 （in Chinese）.［陳子軍，王璐，劉文遠(yuǎn).路網(wǎng)中互近鄰查詢(xún)處理方法 ［J］.小型微型計(jì)算機(jī)系統(tǒng)，2011，32 （4）：607－609.］