基于動態創建局部Ｖｏｒｏｎｏｉ圖的連續近鄰查詢
2008-12-31 00:00:00王淼郝忠孝
計算機應用研究 2008年9期
摘 要：在充分認識到k階Voronoi圖在解決連續k個近鄰查詢優越性和現實不可行性的基礎上，用分支限界的思想去界定預創建Voronoi圖生成點范圍的上界，提出了一種動態地創建局部Voronoi圖的辦法解決連續近鄰查詢問題。該方法只是在給定查詢段上所有點的k個近鄰范圍上界內創建一個局部的k階Voronoi圖，這樣大大降低了基于Voronoi圖的連續k近鄰查詢的代價。
關鍵詞：連續近鄰查詢； k階Voronoi圖； 時空數據庫
中圖分類號：TP311.131 文獻標志碼：A
文章編號：10013695(2008)09277104
Continuous nearest neighbors queries based on dynamically
constructing local Voronoi diagram
WANG Miao1， HAO Zhongxiao1，2
(1. College of Computer Science Technology， Harbin University of Science Technology， Harbin 150080， China; 2. College of Computer Science Technology， Harbin Institute of Technology， Harbin 150001， China)
Abstract:Based on the conception of division and bound to decide the upper bound of scope of Voronoi generaters，this paper proposed a method whichdynamically construct partial Voronoi diagrams to resolve CNN query.This method takes points of k nearest neighbors of every point on given line segment as generaters to construct a korder Voronoi diagram to resolve k CNN query. Lowered the cost of the continuous k nearest neighbors query based on Voronoi diagrams.
Key words：continuous nearest neighbors inquiry; orderk Voronoi diagrams; spatialtemporal database
移動通信的革命，有效廉宜的定位裝置的廣泛應用以及基于位置服務發展的需要使得連續時空查詢備受關注。本文提及的連續近鄰查詢（CNN）即對于一給定的移動查詢點q和點集P，CNN查詢能準確地監視查詢點q運動過程中的近鄰。對于連續最近鄰查詢，已有一些方法被提出。第一個連續最近鄰查詢算法在文獻[1]被提出，采用取樣的方法，通過在取樣點重復應用最近鄰（NN）查詢算法，為一個移動查詢點找到連續最近鄰。然而，這種方法基于取樣，不同的取樣頻率會影響到結果的精確性。如果取樣頻率過低，結果會不正確；如果取樣頻率過高，則會造成很大的計算量，而且由于沒有精確性的保證，即使很高的取樣頻率仍有可能丟失一些重要的取樣點，以致得到的結果不正確。另外一種不會產生錯誤的方法基于TP[2]查詢這一概念，這種方法避免了取樣的缺點。然而此方法只是基于簡單最近鄰算法的重復應用，需要完成n次NN查詢（n為分割點的數目），因此這種算法的性能并不樂觀。基于Voronoi圖的單個連續近鄰查詢算法在文獻[3]被提出，基于Voronoi圖的連續k近鄰查詢也曾被提出，這類方法雖然精確有效并且思路簡單明晰，但由于高階Voronoi圖的構造代價太高，故這類方法并沒有得到廣泛應用。本文從文獻[1]得到思想啟示，在繼承了以往基于Voronoi圖的連續近鄰研究的基礎上，將分支限界的思想與k階Voronoi圖在解決連續k近鄰問題中的優越性相結合提出了一種動態地創建局部Voronoi圖的辦法解決連續近鄰查詢問題。這種方法只是在給定查詢段上所有點的k個近鄰范圍上界內創建一個局部的k階Voronoi圖，去實現連續k近鄰(kCNN)查詢。這種方法在k相對較大時，其優越性更加突出。因為隨著k的增大構造全局k階Voronoi圖越來越困難。本文提出的算法可以有效地通過一次查詢準確地得出移動點的連續最近鄰并且查詢軌跡可以為任意曲線。
1 預備知識
1.1 連續近鄰查詢問題的定義和描述
定義1 CNN查詢[5]。在n維空間中，給定一個點集合S，查詢點q和一個正數k，k個最近鄰搜索問題是發現一個集合P的子集kNNS（q）={p1，p2，…，pk}，使得對于p∈P，kNNs(q)和r∈kNNs(q)都有D(q，r)≤D(q，p)。其中：P是數據空間，D是距離度量。對于CNN查詢，查詢點q是動態的，上面所給出的定義仍然適用。
定義1描述的連續k近鄰查詢，當k=1時即為連續最近鄰查詢。本文所研究的連續近鄰情形如下：對于一移動查詢點q和一靜態點集P，求移動點查詢點q在給定的查詢軌跡[s，e]上的連續近鄰。在這里查詢軌跡[s，e]意義是廣泛的，它可以代表查詢點過去，也可以是將來某一段運動過程。那么此時連續近鄰查詢就是檢索給定查詢軌跡[s，e]上每個點的近鄰。查詢的結果集可表示為〈R，T〉。其中T是一段軌跡間隔，在這一間隔內，R是近鄰集。一個連續最近鄰查詢例子如圖1:P={a，b，c，d，f，g，h}，查詢的輸出{〈a，[s，s1]〉，〈c，[s1，s2]〉，〈f，[s2，s3]〉，〈h，[s3，e]〉}，這意味著在間隔[s，s1]內點a是最近鄰，在s1時，點c成為[s1，s2]最近鄰。最近鄰產生變化的點(s1，s2，s3)為分割點，SL=[si，si+1]為分割點列表。因此，要完成最近鄰查詢的關鍵在于找出分割點。
1.2 Voronoi圖的定義及簡單性質
定義2 Voronoi圖[4]。給定一組生成點P={p1，…，pn}R2。其中：2 其中：j≠i，j∈In，d(p，pi)為p與pi之間的最小距離（歐氏空間中點p與pi 之間的直線距離）。由pi所決定的區域稱為Voronoi多邊形。而由VD(P)={VP(p1)，…，VP(pn)}所定義的圖形被稱為Voronoi圖。共享相同的棱的Voronoi多邊形被稱為鄰接多邊形，它們的生成點被稱為鄰接生成點。圖2展示了部分Voronoi圖。 性質1[5] 一個點集P的Voronoi圖（VD(P)）是獨一無二的。 性質2[5] 生成點pi的最近鄰在pi的鄰接生成點之中。 性質3[5] 令n和ne分別為生成點和Voronoi棱的數量，則ne≤3n-6。性質4[5] 由性質3所得，每個Voronoi棱由兩個Voronoi多邊形所共享，而每個Voronoi多邊形的Voronoi棱的平均數目最多是6。因此，每個生成點最多有6個鄰接的生成點。 定義3 k級鄰接生成點。給定一組生成點P={p1，…，pn}R2生成的Voronoi圖。其中：2 a)一級鄰接生成點。AG1(pi)={pj|VP(pi)和VP(pj)有公共邊}。 b)k(k≥2)級鄰接生成點。AGk(pi)={pj|VP(p)和VP(pj)有公共邊， p∈AGk-1(pi)}。 舉例說明，在圖2中p4的一級鄰接生成點為p1、p2、p6、p7，二級鄰接生成點為p3、p5。 定理1[5] 對于Voronoi多邊形VP(p)內任一點q，那么對于q的第k+1個近鄰pk+1有pk+1∈AG1(p)…∪AGk(p)（k≥1）。 1．3 k階Voronoi圖的定義(k為整數，且1≤ k k階Voronoi圖主要研究平面上給定的包含n個點的點集中任意k個點形成的子集間的最鄰近問題，它能夠有效地解決給定查詢點的k近鄰查詢問題，在理論和實際應用中起著相當重要的作用。它是對定義1所述Voronoi圖在平面上的進一步推廣，將普通Voronoi圖中的生成元由一點擴大至可含有k個點的點集，也就是將定義1所述Voronoi圖作為k階Voronoi圖當k=1時的一個特例。由此可見，k階Voronoi圖的出現，大大擴展了Voronoi圖的研究范圍，開辟了新的更為廣闊的應用領域。下面給出k階Voronoi圖的定義。 定義 4 k階Voronoi圖[4]。設E為歐氏平面，P是E上一個n個點的集合。假設任何四點不共圓，任何三點不共線。設P={p1，p2，…，pn}為二維歐氏空間（平面）上的點集，t是P中任意k(1≤k VPk(t)={P｜v∈t，w∈P-t，d(p，v)＜d(p，w)} 其中：d(p，v)表示點p到點v的Euclid距離。顯然，V(t)是那些到P中任意點v比到s-t中任意點w都近的點的集合。k階Voronoi圖是P中所有這樣的t所形成的區域的并，記做VDk(P)，即VDk(P)=∪VPk(t)，tP，｜t｜=k。當k=1時，即為定義1所給出的Voronoi圖。k階Voronoi圖的頂點和邊分別稱為k階Voronoi頂點和k階Voronoi邊（Voronoi edge）。共享相同的棱的Voronoi區域被稱為鄰接Voronoi區域。它們的生成點被稱為鄰接生成點。 性質5[6] 令n和ne分別為k階Voronoi圖的生成點和k階Voronoi棱的數量，則ne<3kn-3k(k+1)/2。 推論 每個k階Voronoi棱由兩個k階Voronoi多邊形所共享。由性質5可得，每個k階Voronoi多邊形的k階Voronoi棱的平均數目最多是6k2。 2 基于Voronoi圖的連續最近鄰查詢算法 在Voronoi圖中，平面被分割成n個區域，生成元Pi所在的區域是由平面上到Pi的距離比到其他生成元的距離都近的點構成。這時，對平面上任一點P，若要查找Pi(i=1，2，…，n)中距P最近的點，只要看P落在哪個生成元所在的區域即可。那么對于給定查詢軌跡[s，e]的連續最近鄰查詢就轉換為求給定的軌跡與Voronoi圖的交點。這些交點就是要求的分點。 由以上論述可得出基于VR樹索引結構的CNN查詢算法如下: CNN_SEC(n，s，e) 輸入：VR樹節點類型數據n，查詢段的始點s，終點e 輸出：連續近鄰分點列表SL begin callT←NN_SEC(n ，s);//查找s的最近鄰 S←s; /*以下部分為[s，e]基于全局Voronoi圖，求連續最近鄰分點列表的過程*/ while (eVP(T)) do {for Voronoi edge∈VP(T) do if(Voronoi edge∩[S，e]≠ then SL←〈T，[S，edge∩[S，e]]〉 S←edge∩[S，e]; for P∈AG1(T) do if(VP(T)∩VP(P)=edge)then T←P; } //繼續尋找下一個分點 SL←〈T，[S，e]〉; return SL; end 一個基于一階Voronoi圖的連續最近鄰查詢的例子如圖2所示。由圖2知查詢軌跡為[s，e]，查詢結果為分點列表SL={〈p4，[s，b1]〉，〈p6，[b1，b2]〉，〈p3，[b2，e]〉}。 定理2 算法。CNNSEC()算法是可終止的并且能正確求出給定查詢段連續最近鄰分點列表。時間復雜度為O(log n+36i)(i為查詢軌跡穿過Voronoi單元的個數)。 證明 可終止性。本算法調用的過程NN_SEC( )其可終止性在定理1已證明。余下部分的循環操作僅有while…do語句，其結束的條件為e∈VP(T)，其內嵌的雙重for循環語句可自行結束。故該算法是可終止的。 正確性。首先執行NN_SEC(n ，s)找到查詢段始點s的最近鄰，while…do語句以查找到的最近鄰為循環的起點查找[s，e]穿過的所有Voronoi單元，每次循環查找一個沿s→e方向的Voronoi單元并將連續最近鄰列表的一個元組存入SL。循環結束后SL保存著連續最近鄰分點列表，所以該算法實現了查找交點并存儲近鄰信息的過程。故該算法是正確的。 時間復雜度分析。執行NN_SEC(n ，s)過程的時間復雜度為O(log n)級。由一階Voronoi圖的性質4知每個Voronoi單元平均有6條邊，嵌套的for語句最多執行6×6=36次。最外層的while…do語句要循環i(i為查詢軌跡穿過Voronoi單元的個數)次。所以該算法的時間復雜度為O(log n+36i)。 3 基于動態創建局部k階Voronoi圖的連續k近鄰 查詢算法 k階Voronoi圖能有效地解決給定查詢段的連續k近鄰查詢，但構造一個全局的k階Voronoi圖代價太大。本文提出了一種動態地創建局部k階Voronoi圖的辦法解決連續k近鄰查詢問題。該方法僅在給定查詢段上所有點的k個近鄰范圍上界內創建一個局部的k階Voronoi圖，實現連續k近鄰查詢(kCNN)。下面給出由一階Voronoi圖的性質得出的一個定理，它為確定給定查詢段上所有點的k個近鄰范圍的一個上界提供了理論依據。 定理3 對于整個數據空間P={p1，p2，…，pn }的Voronoi圖VD(P)和一給定查詢軌跡[s，e]，若VD(P)∩[s，e]≠，則[s，e]上每一點的前k個近鄰必在{AG1(pi)…∪AGk-1(pi)｜VP(pi)∩[s，e]≠}中。 證明 VD(P)∩[s，e]≠，則[s，e]被VD(P)分成一線段集{Li︱VP(pi)∩[s，e]=Li}由定理1知VP(pi)內任一點q，q的第k個近鄰pk∈AG1(pi)…∪AGk-1(pi)（k≥1），那么q前k個近鄰都在AG1(p)…∪AGk-1(p)內，故Li上每點的前k個近鄰都在AG1(p)…∪AGk-1(p)。故{Li︱VP(pi)∩[s，e]=Li}，即[s，e]上每一點的前k個近鄰必在{AG1(pi)…∪AGk-1(pi)︱VP(pi)∩[s，e]≠}中。證畢。 由定理3知，對于給定查詢軌跡[s，e]上所有點的k近鄰必在[s，e]穿過的所有一階Voronoi多邊形生成點的前k-1階鄰接生成點中。本算法的基本思想是：由定理3確定了給定查詢段上所有點k個近鄰所在范圍的一個上界集合。那么以這個上界集合為生成點生成一個局部的k階Voronoi圖是足以能夠通過求查詢段與該k階Voronoi圖的交點，正確地得到連續k近鄰查詢分點列表。因為查詢軌跡上每一點的k近鄰都在該局部的k階Voronoi圖的生成點之中。 整個查詢過程步驟如下： a)求出由定理3確定的給定查詢軌跡上所有點的k近鄰范圍中限點集。 b)以第二步查找到的點集合為生成點，生成一個局部的k階Voronoi圖。 c)求查詢段與第三步生成的Voronoi圖的交點，輸出查詢結果。 由以上論述可得出基于動態創建局部k階Voronoi圖的kCNN查詢算法如下: FIND(n，s，e)/*求由定理3確定的[s，e]上所有點的k近鄰范圍上界點集*/ 輸入：VR樹節點類型數據n，查詢段的始點s，終點e 輸出：[s，e]上所有點k近鄰所在范圍的一個上界點集Q begin callT←NN_SEC( n ， s);//查找s的最近鄰 S←s; while (eVP(T)) do //繼續尋找查詢段穿過的下一個Voronoi多邊形 {for Voronoi edge∈VP(T) do if(Voronoi edge∩[S，e]≠) then S←edge∩[S，e]; for P∈AG1(T) do if(VP(T)∩VP(P)=edge) then T←P; Q←Q∪AG1(T)∪…∪AGk-1(T);} Q←Q∪AG1(T)∪…∪AGk-1(T); return Q; end kCNNSEC(n，s，e，k) 輸入：VR樹節點類型數據n，查詢軌跡始點s，終點e，查詢近鄰的個數k 輸出：分點列表SL begin Q=Ф， SL=Ф;//SL為分點列表 call K←FIND(n，s，e)//求預生成k階Voronoi圖的生成點 call VDk(K)←ge kVoronoi(Q，k); //生成局部k階Voronoi圖(文獻[6]) callT←kNN_SEC(n，s);//查找s的k近鄰 S←s; /*以下部分為[s，e]基于動態創建的局部k階Voronoi圖VDk(P)，求連續k近鄰分點列表的過程*/ while (eVPk(T)) do{ for Voronoi edge∈VPk(T) do if(Voronoi edge∩[S，e]≠) then SL←〈T，[S，edge∩[S，e]]〉 S←edge∩[S，e]; for P∈AG(T) do //生成元點集T的鄰接生成元點集簡記為AG(T) if((VPk(T)∩VPk(P)=edge)then T←P;}//繼續尋找下一個分點 SL←〈T，[S，e]〉; returnSL; end 定理4 算法KCNNSEC()算法是可終止的并且能正確地求出給定查詢段連續k近鄰分點列表，時間復雜度為O(2 log n+36i+36jk4+eloge+ek2)級 (n為全局數據點的數目，i﹑j分別為查詢軌跡[s，e]穿過一階、k階Voronoi單元的數目，e為局部k階Voronoi圖生成點的數目)。 證明 可終止性。本算法調用的子過程FIND()與CNN_SEC()語句結構一樣，CNN_SEC()可終止，故FIND()也可終止。余下的部分循環操作僅有while…do語句，其結束的條件為eVPk(T)，其內嵌的雙重for循環語句，可自行結束。故該算法是可終止的。 正確性。FIND()過程首先執行NN_SEC(n，s)找到查詢軌跡的始點的最近鄰，并將最近鄰的前k-1階鄰接生成點存入Q；while…do語句以查找到的最近鄰為循環的起點實現了查找[s，e]穿過的所有Voronoi單元，每次循環查找到一個沿s→e方向上Voronoi單元并將它的生成點的前k-1階鄰接生成點存入Q。執行FIND()實現了第一步的要求：求出由定理7確定的給定查詢段所有點k近鄰范圍上界點集。執行ge kVoronoi(Q，k)生成了以上限點集合為生成點的局部k階Voronoi圖。while…do語句，它以起點s所在的k階Voronoi單元為循環的起點查找[s，e]穿過的所有k階Voronoi單元，每次循環查找一個沿s→e方向的k階Voronoi單元并將連續近鄰分點列表的一個元組存入SL。循環結束后SL保存著分點列表，所以該算法實現了查找[s，e]與局部k階Voronoi圖交點并存儲連續k近鄰分點列表的過程。故該算法是正確的。時間復雜度分析。對有n個點的數據空間執行kNNSEC()過程的時間復雜度為O(log n)級；調用的子過程FIND()與CNN_SEC()語句結構一樣，故它們時間復雜度均為O(log n+36i)級；若執行FIND()得到點的數目為e，那么執行ge kVoronoi(Q，k)過程的時間復雜度為O(e log e+ek2)[6]級。對于余下的部分，由性質5的推論知每個k階Voronoi單元平均最多有6k2條邊，所以嵌套的for語句最多循環36k4次。最外層的while…do語句要循環j(j為[s，e]穿過k階Voronoi單元的數目)次。所以該部分至多循環36jk4次。故該算法的時間復雜度為O(2log n+36i+36jk4+e log e+ek2)級(n為全局數據點的數目，i﹑j分別為[s，e]穿過一階﹑k階Voronoi單元的數目，e為局部k階Voronoi圖生成點的數目)。 本算法利用一階Voronoi圖中各級鄰接生成點和近鄰的關系，確定了給定查詢軌跡上所有點的k近鄰所在的范圍的一個上界。基于這個上界內的點構造一個局部的k階Voronoi圖而不是全局的Voronoi圖，故基于Voronoi圖的連續k近鄰查詢算法的時間復雜度降低。 4 結束語 k階Voronoi圖在解決連續k近鄰查詢問題中有其優越性。基于k階Voronoi圖的連續近鄰查詢可以有效地通過一次查詢得出移動點的連續最近鄰，它解決問題的思想簡單明晰。但由于時空數據庫中數據龐大，要對全局數據構造一個高階Voronoi圖去實現連續k個近鄰查詢，代價太大沒有實現可行性。本文提出了一種動態地創建局部Voronoi圖的辦法。該方法不是以整個數據空間而是以某些特定的點為生成元創建一個足以實現給定查詢段連續k近鄰查詢的局部Voronoi圖。該方法大大降低了查詢的時間復雜度。本文的主要貢獻就是提出了基于創建局部Voronoi圖解決連續近鄰查詢的思想。那么尋找新的﹑更行之有效的限界方法將預生成Voronoi圖生成點的范圍上限界定在盡可能小的范圍內將是本課題未來研究的重點。 參考文獻： ［1］SONG Z， ROUSSOPOULOS N. kNN search for moving query point[C]//Proc of the 7th SSTD Symposium.Redondo Beach，CA:Springer，2001:7996. [2]TAO Yufei，PAPADIAS D. Timeparameterzied queries in spatiotemporal databases[C]//Proc ofSIGMOD Conference.2002:334345. [3]BESPAMYATNIKH S， SNOEYINK J. Queries with segments in Voronoi diagrams[J].SODA，1999:122129. [4]LEE D T. On knearest neighbor Voronoi diagrams in the plane[J].IEEE Trans on Computers，1998，31:478487. [5]KOLAHDOUZAN M， SHAHABI C. Voronoibased knearest neighbor search for spatial network databases[C]//Proc of VLDB. Toronto， Canada:[s.n.]，2004. [6]MEYERHENK H. Constructing higherorder Voronoi diagrams in parallel[C]//Proc of EWCG.[S.l.]:Eindhoven，2005:5660. [7]GUTTMAN A. Rtrees: a dynamic index structure for spatial searching[C]//Proc of ACM SIGMOD Conf Ann Meeting. 1984:4757. [8]TAO Yufei，PAPADIAS D，SHEN Qiongmao. Continuous nearest neighbor search[C]//Proc of the 28th VLDB Conference.2002:287298.
