劉大有，呂倩楠，王生生

吉林大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，長春130012

反 k近鄰 (reverse k nearest neighbor，RkNN)查詢自提出后，受到數(shù)據(jù)庫界的廣泛關(guān)注，它在決策支持、資源配置、數(shù)據(jù)挖掘及基于剖面的市場分析等領(lǐng)域有著重要的應(yīng)用價值［1］.一個對象很可能從其近鄰請求服務(wù)，若提供服務(wù)的對象知道哪些對象期望服務(wù) (進(jìn)行RkNN查詢)，就可有針對性地采取應(yīng)對措施.求助服務(wù)的對象可以是戰(zhàn)場上的戰(zhàn)士，危險環(huán)境下的游客等;提供服務(wù)的對象可以是各種救助人員.例如，某城市發(fā)生多起事故，救助人員或相關(guān)執(zhí)法人員可通過反k近鄰查詢對事故現(xiàn)場進(jìn)行及時處理.

Korn等［2］提出反近鄰查詢并給出一種依賴預(yù)處理的查詢方法，但該方法不能有效更新數(shù)據(jù)庫.Stanoi等［3］提出無需預(yù)處理的6區(qū)域剪枝法，但該方法只適于2維空間.TAO等［4］將該方法擴(kuò)展到解決k＞1的情況;并且利用垂直平分線特性，提出TPL剪枝法，但當(dāng)k較大時該方法計算量較大，不適于計算能力弱的設(shè)備.Singh等［5］基于對象的近鄰很可能成為其反近鄰的觀點(diǎn)，提出SFT方法，但該方法結(jié)果不精確.WU等［6］提出利用垂直平分線在平面上形成凸多邊形進(jìn)行剪枝的方法，但該方法同樣只適用于2維空間.此外，還有學(xué)者研究了連續(xù)反 k近鄰 (continuous reverse k nearest neighbor，CRkNN)查詢［4，7-9］.

本研究提出一種新的RkNN查詢方法，采用過濾-精煉兩步式處理方法［10］，在過濾階段采用兩種新的計算量小且剪枝率高的剪枝啟發(fā)式，可有效處理數(shù)據(jù)庫更新，適用于任意k值、任意維的對象集，查詢結(jié)果精確且計算量小.通過對4個真實數(shù)據(jù)庫的仿真對比實驗，發(fā)現(xiàn)當(dāng)k＞6時基于R樹結(jié)點(diǎn)覆蓋值 (R-tree's cover-value，RC)反k近鄰查詢時間更短.

1 相關(guān)知識

1.1 基本定義

設(shè)多維對象集P，查詢點(diǎn)q?P，對象p∈P，o∈P.dist(q，p)表示q和p之間的歐幾里得距離.

定義1 k近鄰查詢，記作kNN.p是kNN(q)的查詢結(jié)果，當(dāng)且僅

q的反k近鄰與k近鄰無直接聯(lián)系［4］，如圖1.對象集 P={p1，p2，p3，p4}，查詢點(diǎn)為 q，2NN(q)={p1，p3}但 R2NN(q)={p3，p4}.

圖1 近鄰和反近鄰的例子Fig.1 Examples of 2NN and R2NN

1.2 R樹索引結(jié)構(gòu)

速度是數(shù)據(jù)集查詢的關(guān)鍵指標(biāo)之一，而使用索引是提高速度的核心技術(shù).Guttman［11］提出的R樹是B樹在k維空間上的擴(kuò)展，由中間結(jié)點(diǎn)和葉結(jié)點(diǎn)組成.葉結(jié)點(diǎn)存儲實際空間對象的最小邊界矩形(minimum bounding rectangle，MBR)，中間結(jié)點(diǎn)存儲其子結(jié)點(diǎn)的MBR.其中，實心點(diǎn)為數(shù)據(jù)對象、矩形為結(jié)點(diǎn)的MBR.我們將以圖2(a)所示的2D數(shù)據(jù)空間為例進(jìn)行介紹，圖2(b)為對應(yīng)的R樹索引結(jié)構(gòu).

圖2 2維數(shù)據(jù)空間和R樹Fig.2 2D dataspace and corresponding R-tree

2 RC-反k近鄰查詢方法

對R樹索引的數(shù)據(jù)集進(jìn)行查詢，一般采用過濾-精煉兩步式處理方法［10］:過濾階段將排除非查詢結(jié)果的對象，并得到候選集;精煉階段將進(jìn)一步確認(rèn)候選集中的對象，并得到精確結(jié)果集.過濾階段是重點(diǎn)，因此現(xiàn)有的大部分反k近鄰查詢方法都是針對過濾階段進(jìn)行的研究.本研究在過濾階段采用兩種剪枝啟發(fā)式排除非查詢結(jié)果的對象，并將得到的候選集作為精煉階段的輸入.

精煉階段有兩種處理方法［6］:一是利用kNN查詢，對候選對象進(jìn)行kNN查詢，若候選對象到第k近鄰的距離不小于到q的距離，則該候選對象即為所求;二是利用 range－k(q，p)，若結(jié)果為真，則該候選對象即為所求.但這兩種方法都需在精煉階段遍歷R樹.本研究提出的RC-反k近鄰查詢方法采用TPL精煉方法［4］，可記錄過濾階段剪枝的R樹結(jié)點(diǎn)和數(shù)據(jù)對象，對于它們不需再次訪問外存，從而減少了I/O操作.

RC-反k近鄰查詢方法需在建立R樹時為每個結(jié)點(diǎn)預(yù)計算cover值［12］.其中，cover值為以該結(jié)點(diǎn)為根的子樹所包含數(shù)據(jù)對象的個數(shù).如圖2，cover(N1)=2，cover(N3)=4.該預(yù)處理過程簡單，只需在插入過程中將插入路徑 (從根到葉節(jié)點(diǎn))上的每個R樹結(jié)點(diǎn)的cover值加1，顯然該預(yù)處理可很好地應(yīng)對數(shù)據(jù)庫更新.

2.1 剪枝啟發(fā)式

對R樹索引的數(shù)據(jù)集進(jìn)行反k近鄰查詢時需遍歷R樹，又因R樹存儲在外存中，所以加快查詢速度的關(guān)鍵在于減少訪問R樹結(jié)點(diǎn)的個數(shù)，降低I/O開銷.若通過當(dāng)前結(jié)點(diǎn)可判斷出以該結(jié)點(diǎn)為根的子樹不包含所求對象，則該結(jié)點(diǎn)被剪枝，無需繼續(xù)訪問該結(jié)點(diǎn)的子結(jié)點(diǎn).下面我們將主要討論如何對R樹結(jié)點(diǎn)進(jìn)行剪枝，即判斷R樹結(jié)點(diǎn)包含的對象并非所求.

總結(jié)反k近鄰剪枝的本質(zhì):設(shè)數(shù)據(jù)對象集為P，查詢點(diǎn)q?P，對象p∈P，若可在P找到k個對象到p的距離小于q到p的距離，即使這些對象不是p的k近鄰，但通過它們可判定q非p的k近鄰，即p非q的反k近鄰.

2.1.1 剪枝啟發(fā)式Ⅰ

剪枝啟發(fā)式Ⅰ基本思想:若數(shù)據(jù)空間中某個區(qū)域R內(nèi)含n(n＞k)個對象，該區(qū)域內(nèi)的對象相互接近 (即對于R中任一對象p，R中至少存在其他k個對象比q更接近p)，則R中不可能包含q的RkNN.

引理1 當(dāng)結(jié)點(diǎn)N的cover(N)≥k+1，且mindist(N，q)＞diag(N)，則結(jié)點(diǎn)N被剪枝.其中，mindist(N，q)是結(jié)點(diǎn)N的MBR到q的最小距離，diag(N)是結(jié)點(diǎn)N的MBR對角線.圖3為剪枝啟發(fā)式Ⅰ的示意圖.

圖3 剪枝啟發(fā)式ⅠFig.3 Pruning heuristic methodⅠ

【證】結(jié)點(diǎn)N中對象p到N中其他對象p'的距離為 dist(p，p')≤ diag(N)，又有 mindist(N，q)≤dist(p，q).若 diag(N)＜ mindist(N，q)，則 dist(p，p')＜dist(p，q).若N中存在≥k個數(shù)據(jù)對象到p的距離小于q到p的距離，則p非q的RkNN.

不能被剪枝啟發(fā)式Ⅰ剪枝的情況有:①cover(N)≤k;②cover(N)＞k，且q和N的位置關(guān)系如圖4，其中，q在淺灰色區(qū)域中;虛線長度為diag(N).

圖4 當(dāng)cover(N)＞k時N不被剪枝的情況Fig.4 The case that N is not pruned when cover(N)＞k

綜上可知，剪枝啟發(fā)式Ⅰ計算量很小，剪枝效率較高，大部分?jǐn)?shù)據(jù)對象都可被剪枝啟發(fā)式Ⅰ排除.如圖2，當(dāng)k=1時，結(jié)點(diǎn)N12、N2和N4都被剪枝.

2.1.2 剪枝啟發(fā)式Ⅱ

剪枝啟發(fā)式Ⅱ基本思想:若數(shù)據(jù)集空間中某區(qū)域R內(nèi)含n(n≥k)個對象，某個數(shù)據(jù)對象p?R到該區(qū)域的最大距離小于到q的最小距離，即R中至少存在k個對象更接近p，則p非q的RkNN.

引理2 當(dāng)結(jié)點(diǎn)N的cover(N)≥k，且結(jié)點(diǎn)N和q的位置關(guān)系如圖5(q處于粗實線左下方)，則圖5中處于陰影部分的結(jié)點(diǎn)被剪枝.

圖5 剪枝啟發(fā)式ⅡFig.5 Pruning heuristic methodⅡ

【證】陰影部分中對象p到結(jié)點(diǎn)N的最遠(yuǎn)距離是dist(A，p)，線段qp交BA的延長線于點(diǎn)E，顯然dist(q，p)＞dist(E，p)且dist(E，p)≥dist(A，p)，則dist(q，p)＞dist(A，p).又因dist(A，p)是結(jié)點(diǎn)N到p的最遠(yuǎn)距離，顯然N中的對象到p的距離小于dist(q，p)，其中cover(N)≥k，則對于陰影內(nèi)的對象至少找到k個對象比q離p近，所以陰影內(nèi)的結(jié)點(diǎn)或?qū)ο蟛皇莙的RkNN.

為了提高剪枝啟發(fā)式Ⅱ的效率，本研究以q為中心劃分整個數(shù)據(jù)空間.下面以2維空間為例進(jìn)行介紹.

如圖6，首先將整個2維數(shù)據(jù)空間以q為中心劃分為 4部分，并為每部分找出矩形 N，使cover(N)=k.然后，在每部分分別應(yīng)用剪枝啟發(fā)式Ⅱ，則各部分都會形成一個陰影區(qū)域，陰影區(qū)域中的對象不是q的RkNN.為達(dá)到更大的剪枝效率，形成大陰影區(qū)域，在每部分中選取離q較近的k個對象，用這k個對象形成矩形N.因為RC-反k近鄰查詢方法使用了基于最小距離的優(yōu)先堆棧H(基于對象的近鄰很可能成為它的反近鄰這種直觀想法)，而H中的項按照到q的最小距離從小到大排序，所以每部分的前k個數(shù)據(jù)對象即所選對象.

圖6 2維空間中使用剪枝啟發(fā)式ⅡFig.6 Using pruning heuristic methodⅡin 2D space

由圖6可見，僅R樹結(jié)點(diǎn) (黑色矩形)完全屬于某部分時才可使用剪枝啟發(fā)式Ⅱ.當(dāng)結(jié)點(diǎn)和N中心點(diǎn)的相對位置與N和q的相對位置一致時，結(jié)點(diǎn)或?qū)ο罂杀患糁l(fā)式Ⅱ剪枝.例如2維數(shù)據(jù)空間中結(jié)點(diǎn)和點(diǎn)的相對位置有4種情況:圖6中R1、R2、R3、R4分別和點(diǎn)q的位置關(guān)系.圖6中矩形BN和點(diǎn)c的相對位置關(guān)系與矩形N和點(diǎn)q的相對位置關(guān)系一樣.

多維數(shù)據(jù)集空間劃分類似于2維，設(shè)維數(shù)為d，則多維數(shù)據(jù)集可劃分為2d個區(qū)域，其相對位置關(guān)系有2d種.

2.2 方法描述

過濾階段使用基于最小距離優(yōu)先的堆棧H保存即將訪問但尚未訪問的R樹結(jié)點(diǎn)或數(shù)據(jù)對象.首先將R樹根結(jié)點(diǎn)壓入堆棧，每次從堆棧中取出一項e進(jìn)行判斷，直到堆棧為空時過濾階段結(jié)束.本研究分兩種情況對取出的項e進(jìn)行判斷.

考慮cover(e)＞k情況.若e可被剪枝啟發(fā)式Ⅰ剪枝，則使用剪枝啟發(fā)式Ⅰ剪枝;若e不能被剪枝啟發(fā)式Ⅰ剪枝且e完全屬于數(shù)據(jù)空間某部分，則使用剪枝啟發(fā)式Ⅱ剪枝;若e不能被上述兩個剪枝啟發(fā)式剪枝，則將e的子結(jié)點(diǎn)壓入堆棧，并進(jìn)入下次循環(huán).

考慮cover(e)≤k情況.①e完全屬于數(shù)據(jù)空間某部分中且是數(shù)據(jù)對象若該部分尚未形成剪枝矩形，則將其插入該矩形集合，用來形成剪枝矩形;若該部分已形成剪枝矩形，且剪枝啟發(fā)式Ⅱ成功，則將其插入到剪枝集合Strim;否則，需判斷該數(shù)據(jù)對象到剪枝矩形的最大距離是否小于到q的距離，若小于則插入Strim，否則插入候選集Sscnd.②e完全屬于某部分且是R樹結(jié)點(diǎn)，若該部分已形成剪枝區(qū)域且可被剪枝啟發(fā)式Ⅱ成功剪枝，則插入Strim.③e不完全屬于某部分且是數(shù)據(jù)對象，則插入Sscnd.④若以上情況皆不是，則將e的子結(jié)點(diǎn)插入到堆棧H中.

RC-反k近鄰查詢方法過濾階段的描述如圖7.

過濾階段結(jié)束后得到的候選集Sscnd和剪枝集合Strim作為精煉階段的輸入.在精煉階段本研究選用TPL的精煉方法［4］，其基本原理可描述為:① 設(shè)候選集中點(diǎn)為p，若候選集中存在另一點(diǎn)p'使dist(p，p')＜dist(p，q)，則p非所求;② 設(shè)候選集中點(diǎn)為p，若Strim中存在點(diǎn)p'使得dist(p，p')＜ dist(p，q)，則p非所求;③設(shè)候選集中點(diǎn)為p，若Strim中存在結(jié)點(diǎn) N使 得 minmaxdist(p，N) ＜ dist(p，q)(minmaxdist(p，N)代表p到N中點(diǎn)的最小距離的上限)，則 p非所求;④ Strim中的結(jié)點(diǎn) N，若mindist(p，N)≥dist(p，q)，則可以確定p是所求;否則該候選點(diǎn)在這次循環(huán)中無法確定，并記錄所有mindist(p，N)＜dist(p，q)的N供下次循環(huán)使用，直到候選集為空時精煉階段結(jié)束.

圖7 RC-反k近鄰查詢方法過濾階段算法描述Fig.7 Algorithm of RC-RkNN in the filter step

3 實驗分析

為分析算法的執(zhí)行性能，我們通過仿真對比本研究所提出的RC-反k近鄰查詢方法與TPL方法的查詢結(jié)果.仿真實驗在雙核2.8 GHz處理器、1 GB內(nèi)存和Microsoft Windows XP professional操作系統(tǒng)的PC機(jī)上完成.RC-反k近鄰查詢方法和TPL方法使用C語言實現(xiàn).數(shù)據(jù)采自美國Long Beach地理位 置 LB(http://www.census.gov/geo/www/tiger)、地勢圖數(shù)據(jù) Hypsogr(http://www.rtreeportal.org)、美國國家浮標(biāo)中心的三維海浪方向測量Wave(從 http://www.ndbc.noaa.gov)和圖像四維彩色直方圖 Color(http://www.cs.cityu.edu.hk/～ taoyf/ds.html)數(shù)據(jù)集，其信息如表1.本研究使用Spatial-DataGenerator數(shù)據(jù)生成器(http://www.rtreeportal.org/software/SpatialDataGenerator.zip)，生成遵循 U-niform分布和Zipf分布的數(shù)據(jù)集.其中，Uniform數(shù)據(jù)集中每個對象的坐標(biāo)都規(guī)范在［0，10 000］;Zipf數(shù)據(jù)集服從1個偏離系數(shù)為0.8的Zipf分布.以上所有數(shù)據(jù)集中每個數(shù)據(jù)對象的坐標(biāo)在每一維上都是獨(dú)立的，各數(shù)據(jù)集都使用R*樹索引［10］，每個結(jié)點(diǎn)的大小設(shè)定為1 kbytes.

表1 實驗使用的真實數(shù)據(jù)集的統(tǒng)計信息Table 1 Statistics of real datasets

實驗主要評估數(shù)據(jù)分布、k值、數(shù)據(jù)維數(shù)及數(shù)據(jù)基數(shù)對查詢效果的影響.每種查詢方法都進(jìn)行400次 (這400次查詢的查詢點(diǎn)是屬于數(shù)據(jù)集空間的400個點(diǎn))，結(jié)果取其平均值.

首先研究k值對查詢效果的影響.圖8顯示不同k值下，RC-反k近鄰查詢方法和TPL方法在各真實數(shù)據(jù)集中的查詢耗時.其中，查詢耗時分為過濾階段的耗時和精煉階段耗時;a是RC-反k近鄰查詢方法的剪枝啟發(fā)式Ⅰ的剪枝率.由圖8可見，當(dāng)k＞6時，所有數(shù)據(jù)集中RC-反k近鄰查詢方法的查詢時間均小于TPL方法，且因RC-反k近鄰查詢方法的剪枝啟發(fā)式Ⅰ和k值幾乎無關(guān)，所以RC-反k近鄰查詢方法過濾階段耗時變化幅度很小.圖8中的百分比驗證剪枝啟發(fā)式Ⅰ可減掉大部分?jǐn)?shù)據(jù)對象，且剪枝啟發(fā)式Ⅰ的計算量相當(dāng)小，這正是導(dǎo)致RC-反k近鄰查詢方法耗時較短的原因.

圖9顯示數(shù)據(jù)空間維數(shù)對查詢結(jié)果的影響.設(shè)k=8，數(shù)據(jù)集包含104個數(shù)據(jù)對象，分別用2維和3維Uniform和Zipf數(shù)據(jù)集進(jìn)行實驗.由圖9可見，RC-反k近鄰查詢方法和TPL方法的查詢耗時隨數(shù)據(jù)集維數(shù)的增加而增加.這是因為當(dāng)維數(shù)增加時，R*樹效率變低 (同層R*樹結(jié)點(diǎn)的MBR相互重疊比較大［4］).由圖9柱狀圖上方所標(biāo)a值可見，RC-反k近鄰查詢方法中的剪枝啟發(fā)式Ⅰ對Zipf數(shù)據(jù)集比Uniform數(shù)據(jù)集更有效.

圖8 不同k值下RC-反k近鄰查詢方法和TPL方法查詢耗時比較Fig.8 Time consuming of querying by using RC-RkNN and TPL for different k values

圖9 當(dāng)k=8時，2維、3維Uniform和Zipf數(shù)據(jù)集查詢耗時Fig.9 Time consuming of querying for Uniform datasets and Zipf datasets in 2D and 3D when k=8

圖10 為相同數(shù)據(jù)分布、相同數(shù)據(jù)維數(shù)和不同基數(shù)數(shù)據(jù)集的查詢耗時.設(shè)k=8，且2維Uniform和Zipf數(shù)據(jù)集分別包含1×104、2×104、3×104和4×104個數(shù)據(jù)對象.可見，隨著數(shù)據(jù)集基數(shù)的增加，查詢耗時也增加.這是因為當(dāng)數(shù)據(jù)集的基數(shù)增加時，R*樹高度亦增加［10］.

圖10 不同數(shù)據(jù)基的Uniform和Zipf數(shù)據(jù)集查詢耗時Fig.10 Costs of querying Uniform and Zipf datasets in different sizes

結(jié) 語

本研究提出RC-反k近鄰查詢解決方法，采用過濾-精煉兩步式處理方法，在過濾階段提出兩種計算量較小的剪枝啟發(fā)式，并在精煉階段使用TPL精煉方法.RC-反k近鄰查詢方法在k＞6時執(zhí)行的速度比較快，且該方法易于擴(kuò)展解決連續(xù)RkNN問題.今后的工作將主要集中于解決運(yùn)動軌跡的RkNN問題.

［1］高云君.時空數(shù)據(jù)庫查詢處理關(guān)鍵技術(shù)研究［D］.杭州:浙江大學(xué)，2008.

［2］Korn F，Muthukrishnan S.反近鄰查詢的影響集［C］//ACM數(shù)據(jù)管理國際會議論文集.達(dá)拉斯 (美國):ACM計算機(jī)協(xié)會，2000:201-212.(英文版)

［3］Stanoi I，Agrawal D，Abbadi A E.動態(tài)數(shù)據(jù)庫的反近鄰查詢［C］//ACM SIGMOD數(shù)據(jù)挖掘和知識發(fā)現(xiàn)國際會議論文集.達(dá)拉斯 (美國):ACM計算機(jī)協(xié)會，2000:44-53.(英文版)

［4］TAO Yu-fei，Papadias D，LIAN Xiang，等.多維反 k近鄰查詢［J］.超大型數(shù)據(jù)庫國際期刊，2007，16(3):293-316.(英文版)

［5］Singh A，F(xiàn)erhatosmanoglu H，Tosun A.高維反近鄰查詢［C］//第12屆信息和知識管理國際會議論文集.新奧爾良 (美國):計算機(jī)協(xié)會，2003:91-98.(英文版)

［6］WU Wei，YANG Fei，CHAN Chee-Yong，等.Finch:評估位置數(shù)據(jù)的反k近鄰查詢［C］//超大型數(shù)據(jù)庫國際會議論文集.奧克蘭 (新西蘭):超大型數(shù)據(jù)庫有限公司，2008，1(1):1056-1067.(英文版)

［7］Benetis R，Jensen C S，Karciauskas G，等.移動對象的近鄰和反近鄰查詢［C］//國際數(shù)據(jù)庫工程與應(yīng)用會議論文集.［s.l.］:［s.n.］，2002:44-53.(英文版)

［8］Cheema M A，LIN Xue-min，ZHANG Ying，等.更新滯后:連續(xù)管治反k近鄰的有效技術(shù)［C］//超大型數(shù)據(jù)庫會議論文集.里昂 (法國):超大型數(shù)據(jù)庫有限公司，2009，2:1138-1149.(英文版)

［9］XIA Tian，ZHANG Dong-hui.連續(xù)反近鄰查詢的管治［C］//第22屆數(shù)據(jù)挖掘國際會議論文集.華盛頓:IEEE計算機(jī)協(xié)會，2006:77-86.(英文版)

［10］張明波，陸 鋒，申排偉，等.R樹家族的演變和發(fā)展［J］.計算機(jī)學(xué)報，2005，28(3):289-300.

［11］Guttman A.R樹:空間搜索的動態(tài)索引結(jié)構(gòu)［C］//ACM SIGMOD數(shù)據(jù)管理國際會議論文集.紐約:計算機(jī)協(xié)會，1984:47-57.(英文版)

［12］Güting R H，Behr T，XU Jian-qiu.移動對象軌跡的有效k近鄰查詢［J］.超大型數(shù)據(jù)庫國際期刊，2010，19(5):687-714.(英文版)

Abstract:1000-2618(2011)05-0416-EA

? This work was supported by the National Natural Science Foundation of China(60773099，60973088).

［1］GAO Yun-jun.Research on Key Techniques of Query Processing in Spatio-temporal Databases［D］.Hangzhou:Zhejiang University，2008.(in Chinese)

［2］Korn F，Muthukrishnan S.Influence sets based on reverse nearest neighbor queries［C］//Proceeding of the ACM SIGMOD International Conference on Management of Data.Dallas(USA):Association for Computing Machinery，2000:201-212.

［3］Stanoi I，Agrawal D，Abbadi A E.Reverse nearest neighbor queries for dynamic databases［C］//Proceeding of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery.Dallas(USA):Association for Computing Machinery，2000:44-53.

［4］TAO Yu-fei，Papadias D，LIAN Xiang，et al.Multidimensional reverse kNN search［J］.The International Journal on Very Large Data Bases，2007，16(3):293-316.

［5］Singh A，F(xiàn)erhatosmanoglu H，Tosun A.High dimensional reverse nearest neighbor queries［C］//The 12th International Conference on Information and Knowledge Management.New Orleans(USA):Association for Computing Machinery，2003:91-98.

［6］WU Wei，YANG Fei，CHAN Chee-yong，et al.Finch:evaluating reverse k-nearest-neighbor queries on location data［C］//Proceeding of Very Large Data Bases.Ackland(New Zealand):Very Large Data Boses Endowent Inc，2008，1(1):1056-1067.

［7］Benetis R，Jensen C S，Karciauskas G，et al.Nearest neighbor and reverse nearest neighbor queries for moving objects［C］//Proceedings of International Database Engineering and Applications Symposium.［s.l.］:［s.n.］，2002:44-53.

［8］Cheema M A，LIN Xue-min，ZHANG Ying，et al.Lazy updates:an efficient technique to continuously monitoring reverse kNN［C］//Proceeding of the VLDB Endowment.Lyon(France):Very Large Data Boses Endowent I，2009，2:1138-1149.

［9］XIA Tian，ZHANG Dong-hui.Continuous Reverse Nearest Neighbor Monitoring［C］//Proceedings of the 22th International Conference on Data Engineering.Washington:IEEE Computer Society，2006:77-86.

［10］ZHANG Ming-bo，LU Feng，SHEN Pai-wei，et al.The evolvement and progress of R-tree family［J］.Chinese Journal of Computers，2005，28(3):289-300.(in Chinese)［11］Guttman A.R-trees:a dynamic index structure for searching［C］//Proceedings of the ACM SIGMOD International Conference on Management of data.New York:Association for Computing Machinery，1984:47-57.

［12］Güting R H，Behr T，XU Jian-qiu.Efficient k-nearest neighbor search on moving object trajectories［J］.The International Journal on Very Large Data Bases，2010，19(5):687-714.