范圍最近鄰查詢方法研究

劉 彬，王建國(guó)

(1.泰山學(xué)院信息科學(xué)技術(shù)學(xué)院;2.泰山學(xué)院教務(wù)處，山東泰安 271021)

1 引言

最近鄰(Nearest Neighbor，簡(jiǎn)稱NN)查詢是空間數(shù)據(jù)庫(kù)中一種重要的查詢類型，傳統(tǒng)的NN查詢是指查詢離給定點(diǎn)最近的對(duì)象，稱為點(diǎn)的最近鄰(Point NN，簡(jiǎn)稱PNN)查詢［1］.Tao等人提出的連續(xù)最近鄰(Continuous NN，簡(jiǎn)稱CNN)查詢［2］，可以有效地檢索一條線段上所有點(diǎn)的最近鄰，此查詢的輸入限定在一維線段上.

本文提出了二維情形下的最近鄰查詢問(wèn)題——“范圍最近鄰”(Range NN，簡(jiǎn)稱RNN)查詢.在二維情形下，給定一個(gè)數(shù)據(jù)集，RNN查詢檢索矩形里每一個(gè)點(diǎn)的最近鄰.RNN查詢的應(yīng)用比較廣泛，比如在移動(dòng)環(huán)境中，用戶在確定查詢點(diǎn)時(shí)，由于定位方法的原因，他們沒(méi)有辦法找到自己的準(zhǔn)確位置.即使能準(zhǔn)確定位，他們也可能由于個(gè)人原因沒(méi)有辦法將準(zhǔn)確位置提供給服務(wù)商.RNN查詢解決了這個(gè)問(wèn)題，因?yàn)樗樵兊氖欠秶淖罱彾皇屈c(diǎn)的最近鄰.大量的2G/3G移動(dòng)用戶更適合使用這種查詢，因?yàn)檫@些設(shè)備不支持連續(xù)最近鄰，他們可以將RNN查詢闡述成“尋找離城市公園最近的旅社”這樣的問(wèn)題.再如，一個(gè)用戶當(dāng)在附近走動(dòng)的時(shí)候可能會(huì)持續(xù)地尋找最近鄰，向服務(wù)器分別提交這些PNN查詢是低效的.一個(gè)更好的方法是進(jìn)行RNN查詢來(lái)獲得這個(gè)范圍所有可能的最近鄰.在這個(gè)范圍內(nèi)的任何PNN查詢都可以在這個(gè)預(yù)先取出的集合中獲得，這將節(jié)省計(jì)算和通信的代價(jià).這說(shuō)明RNN查詢適用于小范圍內(nèi)的不同用戶進(jìn)行PNN查詢的情形.由于空間鄰近的PNN查詢范圍相同的R樹(shù)結(jié)點(diǎn).如果對(duì)這些點(diǎn)進(jìn)行分組處理，將他們歸屬于不同的范圍，然后進(jìn)行RNN查詢，在RNN的基礎(chǔ)上找到PNN，將會(huì)提高效率.本文主要研究范圍最近鄰查詢的性質(zhì)和基本處理思想.

文章第2部分回顧C(jī)NN查詢的一些相關(guān)知識(shí);第3部分給出RNN查詢的正式定義，分析查詢性質(zhì)，并通過(guò)一個(gè)例子描述了LNN(Line NN)算法的基本處理過(guò)程;第4部分分析LNN算法的時(shí)間復(fù)雜度;最后，提出了一些未來(lái)研究的方向.

2 相關(guān)工作

Song等人在文獻(xiàn)［3］中第一次提出了“連續(xù)最近鄰”查詢的概念，一個(gè)CNN查詢查找一個(gè)移動(dòng)對(duì)象的最近鄰，更具體地說(shuō)，它查找一條線段上所有點(diǎn)的最近鄰.為了處理CNN查詢，Song提出了在線段上反復(fù)對(duì)一些取樣點(diǎn)進(jìn)行NN查詢，在［2］中，Tao等人詳細(xì)說(shuō)明了CNN處理算法.他們證明了這條線段包含一個(gè)“分割點(diǎn)”的集合，其中每一個(gè)分割點(diǎn)有兩個(gè)相同距離的最近鄰對(duì)象，并且這些最近鄰對(duì)象組成了CNN集合.因此，CNN問(wèn)題等價(jià)于遍歷R－樹(shù)時(shí)找到和儲(chǔ)存那些分割點(diǎn)，為了刪除不必要的結(jié)點(diǎn)存取，他們提出了三個(gè)規(guī)則:

1)對(duì)于一中間結(jié)點(diǎn)E和查詢線段q，刪除mindist(E，q)＞SLMAXD的結(jié)點(diǎn)，SLMAXD是所有分割點(diǎn)和它的NN之間距離的最大值.

2)刪除到每一個(gè)分割點(diǎn)s的最小距離比s和s的NN之間距離大的結(jié)點(diǎn).

3)按它們的MINDIST值遞增訪問(wèn)結(jié)點(diǎn).

Tao等人將這些規(guī)則分別通過(guò)廣度和深度優(yōu)先搜索來(lái)實(shí)現(xiàn)，并更進(jìn)一步推廣這些算法來(lái)解決kCNN查詢，kCNN查詢找到的是一條線段上所有點(diǎn)的k個(gè)最近鄰.

3 范圍最近鄰查詢(RNN查詢)

3.1 RNN查詢的定義

定義1 給定一個(gè)二維空間的數(shù)據(jù)集R2，一個(gè)矩形A(邊界在內(nèi))的范圍最近鄰(RNN)的集合可以表示為RNN(A)，即為A中每一個(gè)點(diǎn)的最近鄰(NN)的集合.有:

NN(p)表示點(diǎn)p的最近鄰，A稱為查詢范圍在二維情形下為矩形，當(dāng)它在零－維和1－維空間中，RNN分別變?yōu)镻NN和CNN.

本文采用歐氏距離，這意味著每一個(gè)對(duì)象是一個(gè)點(diǎn)或者可以被一個(gè)點(diǎn)來(lái)代表，因此本文限定數(shù)據(jù)集合于為點(diǎn)數(shù)據(jù)集.

3.2 RNN查詢的性質(zhì)

根據(jù)定義1可知任何一個(gè)A中的對(duì)象是A的一個(gè)RNN，我們稱它為內(nèi)部RNN，因此我們主要是尋找外部RNN，也就是A外的RNN.

圖1 引理1、2、4的證明輔助圖

引理1 一個(gè)對(duì)象p成為A的一個(gè)外部RNN的充要條件是p不在A內(nèi)而是A邊界上的至少一個(gè)點(diǎn)的NN.

證明:必要條件從定義中可以看出是顯然的.充分條件可以通過(guò)反證法來(lái)證明:假定p不是A邊界上的任何一個(gè)點(diǎn)的NN，但p是一個(gè)RNN2，則p至少是A內(nèi)一個(gè)點(diǎn)i的NN，如圖1(a)，i'表示線段和 A邊界的相交點(diǎn).由于p不是i'的NN，則必有另一個(gè)對(duì)象p'使得比短，也就是說(shuō)，，在不等式的兩邊加上，我們得到，這和我們的假設(shè)p是i的NN相矛盾.因此假設(shè)錯(cuò)誤，充分條件得證.

引理1告訴我們查詢A的外部RNN和查詢A邊界上每個(gè)點(diǎn)的NN是等價(jià)的，A的邊界包含四條線段，因此，這個(gè)問(wèn)題就可以轉(zhuǎn)化為查找一條線段L上所有點(diǎn)的NN，這些NN稱為L(zhǎng)的線段最近鄰(LNN).

證明:假定L上有一個(gè)點(diǎn)i，L的NN是p且p'是i的第二最近鄰(如圖1(b))，設(shè)s表示，t表示，取L上一個(gè)小線段

引理2 線段L可以被劃分為有限數(shù)量的小線段，小線段上的每一個(gè)點(diǎn)有相同的NN.，則它上面的所有點(diǎn)的NN為p，因?yàn)樗鼈兊絧的距離總是比s+小，并且它們到p'后其他對(duì)象的距離總是比大.由于L的長(zhǎng)度是有限的且這個(gè)小線段有固定的長(zhǎng)度t－s，因此這些小線段的數(shù)量是有限的.

引理3 如果任何兩個(gè)鄰近的小線段有不同的NN，那么，所有的小線段都有不同的NN.

通過(guò)對(duì)前面引理的證明，引理3是比較明顯的，它說(shuō)明了一個(gè)對(duì)象最多可以成為一條小線段的NN.

引理4 設(shè)e1，e2，…表示從左到右所有小線段的末端點(diǎn)，p1，p2，…表示每條小線段的NN.那么，對(duì)任意i＜j，有pi·x＜pj·x，其中p·x表示對(duì)象p在L上的投影值.

證明:通過(guò)反證法來(lái)證明這個(gè)引理.如果引理不成立，則至少兩個(gè)相鄰的小線段違背這個(gè)規(guī)則，假設(shè)是和，存在·x(見(jiàn)圖2c).因此，pk在的垂直平分線的左邊，而在右邊，那么L上ek左邊的點(diǎn)離比離pk近，反之亦然.這就與是的NN且pk是的NN相矛盾，引理成立.

3.3 算法處理過(guò)程

在這些引理的基礎(chǔ)上，下面通過(guò)一個(gè)例子來(lái)說(shuō)明LNN算法的基本思想.首先通過(guò)對(duì)象p在L上的投影值來(lái)決定要處理的對(duì)象的順序，如圖1所示，處理順序?yàn)閜1，p2，p3，p4，p5(在兩個(gè)或更多個(gè)對(duì)象有相同投影值的情況下，只保留離L最近的對(duì)象).然后，計(jì)算每個(gè)對(duì)象所對(duì)應(yīng)的小線段，如果一個(gè)對(duì)象沒(méi)有相應(yīng)的小線段，這意味著這個(gè)對(duì)象不是一個(gè)LNN.這些小線段的端點(diǎn)可以通過(guò)L和每一對(duì)連續(xù)對(duì)象的垂直平分線的交點(diǎn)來(lái)計(jì)算獲得.在圖1中，最初e1=L.min是p1對(duì)應(yīng)小線段的左端點(diǎn)，當(dāng)處理p2時(shí)，e2作為p2的左端點(diǎn)(也是p1的右端點(diǎn));然而，當(dāng)p3被處理時(shí)的垂直平分線與L相交在e2左邊某個(gè)地方的一個(gè)點(diǎn)，這意味著p2沒(méi)有對(duì)應(yīng)的小線段，因?yàn)閜1或 p3比p2到L上的任何一點(diǎn)要近.因此p2不是一個(gè)LNN，故被移除.這樣p1和p3成為連續(xù)的對(duì)象，p3對(duì)應(yīng)小線段的左端點(diǎn)即被重新計(jì)算，由于位于e2的左端，說(shuō)明上的點(diǎn)距p3比距p1更近，因此e2被移除.接著處理p4，并得到e3作為p4相應(yīng)小線段左端點(diǎn).最后處理p5，但的垂直平分線沒(méi)有與L相交，這意味著p5沒(méi)有小線段，不是一個(gè)LNN.由于p4是保留的最右邊對(duì)象，它的小線段的右端點(diǎn)為e4=L.max，這樣所有點(diǎn)被處理完.得到結(jié)果:p1，p3和p4是LNN，相應(yīng)的小線段是和.

圖2 LNN查詢示例

4 算法性能分析

LNN算法處理過(guò)程分為兩個(gè)階段，第一階段是通過(guò)對(duì)查詢對(duì)象的排序來(lái)決定對(duì)象的處理順序，第二階段是掃描對(duì)象并計(jì)算對(duì)應(yīng)小線段的端點(diǎn).

排序可以使用快速排序方法［4］，在最好情況下花費(fèi)O(nlogn)的時(shí)間代價(jià)，在最壞情況下花費(fèi)O(n2)的時(shí)間代價(jià)，平均時(shí)間代價(jià)通過(guò)推算可以得知為O(nlogn);在掃描過(guò)程中需要計(jì)算小線段的端點(diǎn)，假設(shè)每次計(jì)算的時(shí)間為c(c為任意常數(shù))，則整個(gè)掃描時(shí)間為cn，因此掃描過(guò)程的時(shí)間代價(jià)為O (n).如果程序由兩部分(兩組語(yǔ)句或者兩段代碼)順序組成，我們只需要考慮其中開(kāi)銷較大的部分，因此LNN算法的時(shí)間復(fù)雜度是O(nlogn).

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

文章提出范圍最近鄰(RNN)查詢作為點(diǎn)最近鄰(PNN)和連續(xù)最近鄰(CNN)查詢的擴(kuò)展，并在2D空間中分析了查詢的性質(zhì)，提出了算法基本思想并作了性能分析.未來(lái)的工作將致力于動(dòng)態(tài)數(shù)據(jù)集中范圍最近鄰查詢的研究.

［1］N.Roussopoulos，S.Kelley，F(xiàn).Vincent.Nearest neighbor queries［A］.Proc.of the ACM SIGMOD Intl.Conf.on Management of Data［C］.New York:ACM，1995.

［2］Y.Tao，D.Papadias，Q.Shen.Continuous nearest neighbor search［A］.In Proc.of 28th Intl.Conf.on Very Large Data Bases (VLDB)［C］.Hong Kong:VLDB Endowment，2002.

［3］Z.Song，N.Roussopoulos.K－Nearest Neighbor Search for Moving Query Point［A］.Proc.Symp.Spatial and Temporal Databases［C］.Berlin:Springer，2001.

［4］(美)Clifford A.Shaffer.數(shù)據(jù)結(jié)構(gòu)與算法分析(Java版)［M］.北京:電子工業(yè)出版社，2001.