侯曉琳

（北京大學地球與空間科學學院 北京 100871）

1 引言

反最近鄰查詢是在最近鄰查詢的基礎上提出的一種新的查詢方法。反最近鄰查詢的應用范圍也十分廣泛，主要集中在網(wǎng)絡定位，地理信息系統(tǒng)，地位服務應用，決策系統(tǒng)，文件搜索，數(shù)據(jù)挖掘等方面。隨著計算機技術(shù)發(fā)展，數(shù)據(jù)的表現(xiàn)形式和數(shù)據(jù)量也顯著增加。因此，多維空間反最近鄰查詢算法具有較大的應用價值，成為空間查詢研究中的重點和難點。

1973年，由Knuth提出了最近鄰查詢問題。隨后1995年，N.Roussopoulos等提出k最近鄰查詢問題［1～2］。在最近鄰查詢的研究過程中，相關(guān)領(lǐng)域?qū)＜野l(fā)現(xiàn)了反最近鄰查詢問題和應用前景，提出了反最近鄰查詢。2000年由Flip Korn和S.Muthukrish?nan提出了反最近鄰的相關(guān)概念和解決方法［3］。Congjun Yang等又在前面的基礎上提出了改進的方法，引入了一種新的數(shù)據(jù)結(jié)構(gòu)Rdnn-tree［4］。Amit Singh等提出高維反最近鄰查詢。針對反最近鄰查詢中存在的問題，相關(guān)研究者又提出很多改進方法［5～6］。Rimantas Benetis等提出在平面中連續(xù)移動的點的當前位置和期望位置上的RKNN［7］。由Yufei Tao等提出了任意維的反最近鄰查詢［8］。Mu?Hammad Aamir Cheema等提出了一個有效的技術(shù)Lazy updates，不斷檢測反最近鄰查詢［9］。

由于其具有較大的應用價值，關(guān)于反最近鄰查詢方法仍然在不斷地改進，主要在集中在提升查詢效率和降低查詢成本等方面。

2 空間數(shù)據(jù)和空間裁剪

2.1 空間數(shù)據(jù)與R樹

采用R樹表示和存儲空間數(shù)據(jù)，使用多維元組來表示空間數(shù)據(jù)對象［10］。每個葉節(jié)點中采用指向點數(shù)據(jù)對象的指針的方式存放多個空間數(shù)據(jù)點信息。每個非葉節(jié)點中存放其所包含的子節(jié)點的所有空間數(shù)據(jù)對象的最小矩形，在三維空間中，即使包含其下所有子節(jié)點的最小外包圍六面體。在空間查詢中使用R樹索引結(jié)構(gòu)只需訪問少量的節(jié)點就能確定數(shù)據(jù)點，而不需訪問所有的數(shù)據(jù)。

2.2 線性約束查詢

線性約束查詢目的在于加快搜索的速度，可以快速排除不符合查詢條件的空間對象。在N維空間中，定義空間平面，方程為

將空間分成兩個半空間，半空間的表示形式為

在求N維空間的半空間中，使用兩個點作為已知的條件，然后求出表示相應的半空間的線性約束。在實現(xiàn)過程中使用到了點法式，已知在N維空間 中 兩 點 p，q，其 中 p=(p1，p2，…，pN) ，q=(q1，q2，…，qN)?？梢允褂命c法式求出一個空間N-1維的平面，這個平面通過線段pq的中點，且與線段pq垂直。pq的中點 p′，該空間N-1維的平面的法向量為 (p1-q1，p2-，q2，…，pN-qN)。由此得到的表示多維空間平面的一個線性約束如下：

其中

2.3 空間裁剪方法

使用線性約束對原有空間進行裁剪，以三維空間為例，對裁剪方法加以說明?！?p ，q )是點q和點p之間的垂直平分面，其中點q是查詢點，點p是數(shù)據(jù)集中的任意點?！?p ，q)將整個二維空間分成了兩個半空間。顯然，在包含點p的半空間中的矩形區(qū)域R1中的所有數(shù)據(jù)點到查詢點q的距離都大于到點p的距離，所以R1中的所有點都不是點p的反最近鄰點。假如矩形區(qū)域R1中的一點 p′，p′的最近鄰點是p，不等式成立，所以′不是查詢點q的反最近鄰點。由此可得，經(jīng)過垂直平分線⊥(p ，q)劃分成兩個半空間后，在包含點p半空間中的所有點均不是查詢點q的反最近鄰點。

圖1 三維空間區(qū)域的裁剪

3 反最近鄰查詢算法

3.1 反最近鄰查詢

給定數(shù)據(jù)集S和一個查詢點q，dist（p，q）定義為兩點之間的距離，反最近鄰查詢就是取得S的一個子集RNN（q）：

反k最近鄰查詢（RkNN）：給定數(shù)據(jù)集S和一個查詢點q，dist（p，q）定義為兩點之間的距離，反k最近鄰查詢就是取得S的一個子集RkNN（q）：

其中 pk∈S，并且 pk表示的是q的k最近鄰kNN（q）。

反k最近鄰查詢算法和反最近鄰查詢算法相同采用一個兩步框架算法，第一步是過濾過程，第二部是提純過程。在過濾過程中，首先從數(shù)據(jù)集S中獲得一個子數(shù)據(jù)集S′，作為反k最近鄰的候選集。在這個子數(shù)據(jù)集S′中的數(shù)據(jù)元素有可能是查詢點q的反k最近鄰，也有可能不是查詢點q的反k最近鄰，因此現(xiàn)在獲得的子數(shù)據(jù)集S′還需要獲得進一步的處理，下一步的處理過程就是提純過程。提純過程需要將子數(shù)據(jù)集S′中的數(shù)據(jù)元素進行再次確認，將不是查詢點q的反k最近鄰的數(shù)據(jù)元素，即錯誤命中的數(shù)據(jù)元素拋棄。經(jīng)過提純過程，就可以從子數(shù)據(jù)集S中獲得查詢點q的所有的反k最近鄰。反k最近鄰算法主要由空間裁剪算法，過濾過程和提純過程算法組成。

3.2 裁剪算法

利用裁剪算法主要目的是檢查數(shù)據(jù)點是否在無效區(qū)域內(nèi)，這里所謂的無效區(qū)域指的是一定不包含查詢點的反k最近鄰的區(qū)域。如果數(shù)據(jù)點在無效區(qū)域內(nèi)，則表示該點不屬于目標點的反最近鄰。

在點裁剪算法中，輸入?yún)?shù)是一個數(shù)據(jù)點集和一個待裁剪數(shù)據(jù)點，根據(jù)這個數(shù)據(jù)點集進行裁剪，判斷待裁剪點是否是查詢點的反最近鄰。數(shù)據(jù)點集（其中 m≥k），待裁剪數(shù)據(jù)點p，查詢點q。這里將數(shù)據(jù)點集P中的點看作是查詢點q的可能反k最近鄰，根據(jù)這些點，確定無效區(qū)域。然后判斷待裁剪數(shù)據(jù)點p是否在無效區(qū)域內(nèi)，點裁剪算法將一個距離值作為算法的輸出參數(shù)，如果待裁剪點p在無效區(qū)域內(nèi)，則表示數(shù)據(jù)點p被裁剪掉了，無窮大作為距離值返回；反之，返回點p和點q的距離值。k點裁剪算法的步驟如下：

［步驟1］首先應該求得數(shù)據(jù)集中任意k個數(shù)據(jù)點的半空間平面所組成的空間交集。

［步驟2］根據(jù)數(shù)據(jù)集P中數(shù)據(jù)點的排列順序來獲得k個數(shù)據(jù)點的交空間，第一個交空間是由數(shù)據(jù)點 p1，p2，…，pk形成半空間的交空間，這個交空間就是一個無效區(qū)域。下一個交空間是由數(shù)據(jù)點p2，p3，…，pk+1形成的半空間的交空間。以此類推，最后一個交空間是由數(shù)據(jù)點 pm-k，pm-k+1，…，pm形成的半空間的交空間?？梢垣@得m-k個交空間，這些交空間均為無效區(qū)域。

［步驟3］檢查待裁剪點p是否在這些交空間中。如果在，則表示點p被裁剪掉，一定不是查詢點q的反k最近鄰，以無窮大作為輸出參數(shù)返回。

3.3 過濾算法

在過濾算法中，使用最小堆，集合和R樹等數(shù)據(jù)結(jié)構(gòu)。算法結(jié)束后得到兩個集合，分別是候選集S和檢驗集Sr，圖2描述過濾算法流程。過濾算法的步驟：

［步驟1］初始化最小堆H，此時最小堆中無任何元素。初始化兩個集合，分別是候選集合S和檢驗集合Sr。

［步驟2］首先將R樹中的根插入到最小堆H中。

［步驟3］檢查最小堆H是否為空，如果最小堆H為空，即在最小堆H中在無其他元素，那么算法結(jié)束。如果最小堆不為空，彈出堆頂元素f。這個堆頂元素f可能是數(shù)據(jù)點，可能是R樹的葉節(jié)點，可能是R樹的非葉節(jié)點。

［步驟4］對這個堆頂元素f進行裁剪操作，采用裁剪算法（trim algorithm），如果算法返回的是無窮大值，那么說明堆頂元素完全被裁剪掉了，把f加入檢驗集合Sr中，返回步驟3繼續(xù)執(zhí)行。反之，接著執(zhí)行步驟5。

圖2 過濾算法流程

［步驟5］判斷堆頂元素f的數(shù)據(jù)類型，根據(jù)不同的數(shù)據(jù)類型進行不同的操作。如果堆頂元素f是數(shù)據(jù)點，調(diào)用裁剪算法判斷f是否是可能是查詢點q的反最近鄰，當裁剪算法返回值不是無窮大值時，就將f加入到候選集合S中，作為q的一個反最近鄰，返回步驟3繼續(xù)執(zhí)行。如果堆頂元素f是葉節(jié)點，對于葉節(jié)點f中的每一個數(shù)據(jù)點做下面的操作：調(diào)用裁剪算法判斷數(shù)據(jù)點是否被完全裁剪掉，當數(shù)據(jù)點被裁減掉時，將數(shù)據(jù)點插入到檢驗集合Sr中；當數(shù)據(jù)點未被裁減掉時，計算出查詢點q到數(shù)據(jù)點之間的距離，將數(shù)據(jù)點以查詢點q到數(shù)據(jù)點之間的距離為關(guān)鍵值插入到最小堆中。如果堆頂元素f是R樹的中間節(jié)點，對于中間節(jié)點的每一個孩子節(jié)點做下面的操作：調(diào)用裁剪算法判斷孩子節(jié)點的最小矩形是否被完全裁剪掉。當裁剪算法返回無窮大值時，說明孩子節(jié)點的最小矩形已經(jīng)被完全裁剪掉了，將該孩子節(jié)點插入到檢驗集合Sr中；當裁剪算法返回值不是無窮大值時，說明在孩子節(jié)點的最小矩形中仍有有效區(qū)域，將查詢點q到孩子節(jié)點的最小矩形經(jīng)過裁剪后得到的有效矩形區(qū)域的最小距離作為關(guān)鍵值，將該孩子節(jié)點壓入最小堆H中。

［步驟六］返回步驟3繼續(xù)執(zhí)行。

3.4 提純算法

提純算法為每個數(shù)據(jù)點引進了一個新屬性，這個屬性作為計數(shù)器來用。在提純算法開始之前，首先需要初始化候選集中每個數(shù)據(jù)點的計數(shù)器屬性，初始化的值為k，那么在提純的過程中，一旦發(fā)現(xiàn)候選集中的一個數(shù)據(jù)點到其它某個數(shù)據(jù)點的距離小于該數(shù)據(jù)點到查詢點的距離，就將該數(shù)據(jù)點的計數(shù)器的值減小1，直到當k的值為0時，說明這個數(shù)據(jù)點一定不是查詢點的反k最近鄰，把該點從候選集中刪除。

在循環(huán)提純算法中有四個輸入?yún)?shù)，分別是查詢點q，點檢驗集合Srp，節(jié)點檢驗集合Srr和候選集合S。輸出參數(shù)是查詢點q的反最近鄰集SRKNN。循環(huán)提純算法流程如圖3所示。

圖3 提純算法流程

提純算法流程步驟如下：

［步驟1］從候選集合S中以次序選取一點p，直到S中所有的點都被選取出來過。如果所有的點都被取出來過，算法結(jié)束。

［步驟2］對于點檢驗集合Srp中的每一點 p′，都做以下操作：判斷點p到點 p′的距離是否小于點p到點q的距離。如果點p到點 p′的距離小于點p到點q的距離。則將點p的計數(shù)器counter減小1，檢驗一下此時數(shù)據(jù)點p的計數(shù)器是否為0，如果為0，則說明p點是一個錯誤的命中，將p點從候選集合中刪除，跳到步驟一繼續(xù)執(zhí)行。直到檢驗集合Srp中的所有數(shù)據(jù)點都判斷一次后，繼續(xù)執(zhí)行步驟3。

［步驟3］對于節(jié)點檢驗集合Srr中的每一個節(jié)點R的最小矩形M，都做以下操作：判斷點p到最小矩形M的最大距離是否小于點p到查詢點q的距離，且R中數(shù)據(jù)點的數(shù)量是否大于點p的計數(shù)器counter的值。如果兩個條件都成立的話，即p到最小矩形的最大距離小于點p到查詢點q的矩形，并且R中包含的數(shù)據(jù)點的數(shù)量大于點p的計數(shù)器counter的值，說明p點是錯誤的命中，將p點從候選集合中刪除，跳到步驟一繼續(xù)執(zhí)行。如果Srr中的每個節(jié)點都判斷完畢后，繼續(xù)執(zhí)行步驟四。

［步驟4］對于節(jié)點檢驗集合Srr中的每一個節(jié)點的最小矩形M，都做以下操作：判斷點p到最小矩形M的最小距離是否小于點p到查詢點q的距離。如果小于的話，將節(jié)點加入到點p的Visit集合中，Visit集合是最后為了驗證點點p是否是查詢點q的反最近鄰。

［步驟5］如果點p的Visit集合為空，p就是查詢點q的反最近鄰，將p從候選集合S中刪除，加入到查詢點q的反最近鄰集合SRNN中。

反最近鄰算法結(jié)合R樹，空間裁剪方法，過濾數(shù)據(jù)過程與提純算法過程實現(xiàn)，能夠提高算法效率。

4 算法結(jié)果數(shù)據(jù)驗證

采用兩組數(shù)據(jù)來驗證反最近鄰查詢算法實現(xiàn)結(jié)果。一組是自定義的數(shù)據(jù)，另一組是隨機數(shù)據(jù)，根據(jù)兩組數(shù)據(jù)的實現(xiàn)結(jié)果來驗證反最近鄰查詢算法。采用表1簡單數(shù)據(jù)點進行反最近鄰查詢結(jié)果說明。

表1 簡單實驗數(shù)據(jù)

假設查詢點的模擬坐標為（1，2，1），隨著k取值的不同，反k最近鄰查詢的結(jié)果不同。將所用k的可能的取值所得到結(jié)果如表2所示。

表2 數(shù)據(jù)實驗結(jié)果

若數(shù)據(jù)采用100個二維的隨機數(shù)據(jù)點，由于數(shù)據(jù)點較多并且是隨進產(chǎn)生的，所以不一一列出所有的隨機數(shù)據(jù)點，而是給出二維數(shù)據(jù)點的位置模擬圖4。

圖4 二維數(shù)據(jù)點的位置模擬圖

假設查詢點的模擬坐標為（0，50），得到的查詢點的反最近鄰的結(jié)果如圖5.3所示。查詢點的反最近鄰為id=56的數(shù)據(jù)點（24.32，32.32）和id=75的數(shù)據(jù)點（0.66，88.05），如圖5所示。

圖5 隨機點模擬實驗結(jié)果

5 結(jié)語

目前，反最近鄰查詢技術(shù)已經(jīng)廣泛被應用到很多領(lǐng)域中。本文對反最近鄰查詢和反k最近鄰查詢的相關(guān)技術(shù)研究進行介紹并實現(xiàn)反最近鄰算法中的多維空間裁剪算法，空間過濾算法，提純算法。其優(yōu)點在于支持任意k值的查詢和多維空間的數(shù)據(jù)處理，能夠保證反最近鄰結(jié)果集中數(shù)據(jù)點的準確性，算法實現(xiàn)穩(wěn)定性高，查詢效率較好。

［1］ Nick Roussopoulos，Stephen Kelley，F(xiàn)rederic Vincent.Nearest neighbour queries［J］.Proceedings of the 1995 ACM SIGMOD international conference on Management of Date，1995：71-79.

［2］Sunil Aryan，David M.Mount，Nathan S.Netanyahu，Ruth Silverman，Angela Y.Wu.An optimal algorithm for approx?imate nearest neighbor searching fixed dimensions［J］.Journal of the ACM，1998：891-923

［3］PFlip Korn，PS.Muthukrishnan.Influence Sets Based on Reverse Neighbor Queries［J］.Proceedings of the 2000 ACM SIGMOD international conference on Management of data，2000：201-212.

［4］Congjun Yang，King-Ip Lin.An Index Structure for Effi?cient Reverse Nearest Neighbor Queries［J］.Proceedings of the 17th International Conference on Data Engineering，2001：485-492.

［5］PFlip Korn，PS.Muthukishnan，PDivesh Srivastava.Re?verse nearest neighbor aggregates over data streams［J］.Proceedings of the 28th international conference on Very Large Date Bases，2002：814-825.

［6］Rimantas Benetis，PS.Jensen，Gytis Karciauskas，Simonas Saltenis.Nearest and reverse nearest neighbor queries for moving objects［J］.Proceedings of the 2002 International Symposium on DatabaseEngineering&Applicationg，2002：44-53.

［7］Man Lung Yiu，Nikos Mamoulis.Reverse Nearest Netigh?bors Search in Ad-hoc Subspaces［C］//The 27th Interna?tional Conference on Data Engineering，2006：412-426.

［8］Yufei Tao，Dimitris Papadias，Xiang Lian，Xiaokui Xiao?nei.Multidimensional reverse kNN search［J］.The VLDB Journal，2007：293-316.

［9］Muhammad Aamir Cheema，Xuemin Lin，Ying Zhang，Wei Wang，Wenjie Zhang.Lazy updates：an efficient tech?nique to continuously monitoring reverse kNN［J］.Pro?ceedings of the VLDB Endowment，2009：1138-1149.

［10］鄧紅艷，武芳，翟仁健，等.一種用于空間數(shù)據(jù)多尺度表達的R樹索引結(jié)構(gòu)［J］.計算機學報，2009，32（1）：177-184.DENG Hongyan，WU fang，ZHAI Renjian，et al.R-Tree Index Structure for Multi-Scale Representation of Spatial Data［J］.Chinese journal of computers，2009，32（1）：177-184.