帶權不確定圖的K最近鄰查詢算法

黃冬梅　鄧　斌　趙丹楓

(上海海洋大學信息學院　上海 201306)

?

帶權不確定圖的K最近鄰查詢算法

黃冬梅鄧斌趙丹楓

(上海海洋大學信息學院上海 201306)

摘要社交、移動等復雜網絡節點接入的不確定性給數據查詢處理帶來了新的挑戰。K最近鄰查詢是社交、移動網絡中經常用到的操作。已有的方法首先將網絡映射為不確定圖，然后，考慮邊只含有概率信息的情況。討論了K最近鄰查詢方法，沒有考慮權重信息，具有局限性。針對這個問題，定義了帶權不確定子圖和ProWeiDist距離，兼顧權重和概率兩個要素,提出了針對帶權不確定圖的K最近鄰查詢算法，并對算法進行優化。實驗結果表明，SubDistK算法能有效地解決K最近鄰查詢問題。

關鍵詞復雜網絡不確定數據K最近鄰查詢帶權不確定圖子圖

K-NEAREST NEIGHBOURS QUERY IN WEIGHTED UNCERTAIN GRAPH

Huang DongmeiDeng BinZhao Danfeng

(College of Information,Shanghai Ocean University,Shanghai 201306,China)

AbstractUncertainty of nodes accessing in complex social and mobile networks brings new challenge to data query and processing. K-nearest neighbours query is an operation frequently used over these complex networks. Existing methods map the network to uncertain graph first, and they consider the situation of containing the probability information only.Discussing the K-nearest neighbours query method but do not consider the weight information, therefore have limitations. In view of this problem, we defined the weighted uncertain subgraph and ProWeiDist distance, and proposed a K-nearest neighbours query algorithm targeted at the weighted uncertain graph by incorporating both probability and weight, and further optimised the algorithm. Experimental results demonstrated that the SubDistK algorithm can effectively solve K-Nearest neighbours query problem.

KeywordsComplex networkUncertain dataK-nearest neighbours queryWeighted uncertain graphSubgraph

0引言

快速發展的社交、移動等網絡，由于噪聲控制、隱私保護等原因，產生了大量的不確定數據[1,2]。針對不確定數據的建模有關系型數據[3]、流數據、半結構化數據、移動對象數據等[4]。在蛋白質網絡、社交領域中，圖模型更加適合不確定數據的建模研究[5,6]。其中，查詢對象作為圖的節點，對象之間的關系作為頂點之間的邊，數據間的不確定性成為邊的概率函數。在社交網絡中[7]，每位用戶構成無向圖的一個頂點，用戶之間的關系構成頂點之間的邊。在圖中的每條邊上加入概率信息構成不確定圖，是不確定數據領域研究的一種常用方法。文獻[8]提出不確定圖的“可能世界”語義模型，不確定圖中每條邊都附帶一個介于0和1之間的實數，以表示邊存在的概率，邊的存在概率是相互獨立的。文獻[9]基于不確定圖數據庫提出概率top-k子圖匹配查詢，在查詢過程中，為附帶概率信息的鄰居子圖設計索引結構，在索引結構的基礎上進行查詢。

K最近鄰查詢(KNN查詢)作為一種重要的查詢技術，旨在給定查詢點、查詢對象集合、范圍約束集合以及方向，找到與查詢點距離最近的k個對象[10-12]。針對不確定數據的K最近鄰查詢得到了國內外越來越多人的研究[13-20]。文獻[13]針對蛋白質網絡定義了三種衡量遠近的距離概念，分別為中位距離、大多數距離和期望可信賴距離，應用KNN查詢找到相互作用關系密切的蛋白質群。文獻[14]在可能世界語義基礎上，提出SimRank度量方法，解決由于不確定圖動態演變導致的求k個近鄰開銷過大的問題。文獻[15]定義最短距離概念，提出基于子圖擴展的處理算法。

目前對不確定圖的KNN查詢研究還主要局限于不確定圖只含有概率信息的情況，沒有考慮到權重因素。在復雜網絡如社交網絡中，僅僅用傳統的不確定圖來定義是不恰當的。例如，交友網站的好友推薦系統中，用戶代表圖的節點，系統根據用戶的籍貫、學校、職業、興趣等因素評估用戶間的親密關系，這種好友關系存在的可能性是不確定的，在圖中用頂點間邊的概率表示。但是，用戶在一段時間內的關注和聯系次數是確定的，如果在推薦好友的過程中不考慮關注和聯系次數，查詢結果的準確性會受到影響。因此，需要對傳統的不確定圖進行改進，加入權重的概念。在社交領域中，體現為用戶間一段時間的互動次數；在蛋白質交互領域中[13]，體現為之間產生化學反應的次數。這樣，不確定圖中，邊不僅含有關系代表不確定性的概率，還有可以確定的互動次數的權重。

本文針對帶有權重的不確定圖的查詢問題，進行了以下三點研究：

1) 提出了一種帶權不確定圖上的KNN查詢：GrapKDist查詢；

2) 針對GrapKDist查詢提出了SubDistK算法，并進行優化；

3) 進行實驗證明查詢算法的準確性和高效性。

1基本定義

定義1帶權不確定圖[13]，是一個四元組G=(V，E，P，W)，其中V是無向圖的頂點集合，E=V×V ,為邊的集合；P和W分別為邊的概率和權重函數。?e∈E，P(e)表示邊e的概率，W(e)表示邊e的權重。

圖1是一張帶權不確定圖，共有6個頂點和6條邊，每條邊附帶一個概率值和權重值。每條邊的概率和權重值相互獨立。

圖1　帶權不確定圖

定義2路徑步L(s, t)，帶權不確定圖G=(V，E，P，W)中任意兩個不同頂點s,t∈V，s與t的最短連接路徑中頂點組成的集合Ew，L(s, t)=|Ew|-1。

圖1中，L(A,C)=2，L(A,E)=3，在圖2中，由于點F與A無連接路徑，所以L(A,F)=∞。

定義3源頂點層σ，為一個頂點集合，給定帶權不確定圖G=(V，E，P，W)和查詢源點V0，集合中任意兩個不同頂點s,t∈V，滿足L(V0, s)= L(V0, t)和|σ|<|E|。

圖1中，查詢源點為點A，點C與D到源點A的路徑步都為2，所以同屬一個源頂底層。同樣，點E與F同屬一個源頂點層。而點B與D屬于不同的源頂點層。

定義4ProWeiDist距離，給定帶權不確定圖G=(V，E，P，W)，查詢源點V0，任意頂點Vi∈VV0，dw×p(V0,Vi)衡量頂點Vi與源點V0之間的遠近關系。距離計算方法如下：

ifL(V0,Vi)=1

ifL(V0,Vi)>1&&L(Vk,Vi)=1

ifL(V0,Vi)=∞

dW×P(V0,Vi)=∞

(1)

Ifm=0Rσm=1;

Ifm>0，V∈σm-1Vl∈σm

(2)

定義6帶權不確定圖的K最近鄰查詢：GrapKDist查詢，給定一個帶權不確定圖G=(V，E，P，W)，一個查詢源點V0∈V，查詢目標個數k≤|E|，找到一個擁有k個元素的頂點集合Sk(V0)={v1,…,vk}，?Vi∈Sk(V0)，?Vu∈ESk(V0)，滿足條件的dW×P(Vi)≤dW×P(Vu)。

2SubDistK算法

本節主要針對查詢問題提出兩個定理，并予以證明。依據定理設計查詢方法，在方法基礎上提出了兩個查詢算法。根據算法進行了實例運算。

2.1查詢定理

定理1鄰步定理，帶權不確定圖G=(V，E，P，W)，查詢源點V0，?A,B∈V，且滿足L(V0,B)=L(V0,A)+1，則存在dW×P(B)>dW×P(A)。

證明：

由式(1)和條件L(V0,B)=L(V0,A)+1可得:

(3)

由0

(4)

由式(4)可得：

(5)

結合式(3)、式(5)可得：

dW×P(B)>dW×P(A)

(6)

定理1表明與查詢源點的連接路徑中，兩個相鄰頂點中路徑步越長，則ProWeiDist距離越大。

定理2層次局部性定理，給定帶權不確定圖G=(V，E，P，W)，查詢源點V0，如果存在兩個源頂點層dW×P(si)>dW×P(ti)與σ2，σ1={s1,s2,…,si,…,sn}，σ2={t1,t2,…,ti,…,tm}，滿足條件L(V0,si)=L(V0,ti)+1，則存在R1>R2。

證明：

由條件L(V0,si)=L(V0,ti)+1和定理1可得：

dW×P(si)>dW×P(ti)

(7)

由式(7)可得：

(8)

式(8)結合式(2)可得：

R1>R2

層次局部性定理說明在帶權不確定圖中的兩個相鄰源頂點層，外層的層距離半徑要大于里層。

2.2方法概述

帶權不確定圖中邊同時含有權重和概率，鄰接矩陣不適于作為存儲結構，因此用鄰接鏈表存儲網絡。把圖中所有頂點按照與查詢源點的路徑步大小劃分為不同的源頂點層。 根據層次局部性定理，與查詢源點關系密切的點一般位于路徑步較小的層次中。首先遍歷離源點步長為1的層，對層中節點添加已訪問標識；然后依次增加路徑步值，直到已訪問頂點總數與新源頂點層的和超過參數k；最后形成帶權不確定子圖，在子圖中，根據訪問標識計和頂點路徑步的不同情況，調用式(1)計算ProWeiDist距離。依據距離大小選擇k個節點作為最后的結果。

2.3算法步驟

算法1SubDistK

輸入：帶權不確定圖G=(V，E，P，W)

查詢源點V0∈V

參數k≤|E|

輸出：結果集合Sk

/*初始化路徑步L和中間候選集合S*/

① L=0，S=?;

/*初始化訪問標識*/

② L++; visited=false;

/*遍歷總頂點數為Sum*/

③ 從V0遍歷圖G；Sum=0;

/*即將訪問的源頂點層σL和已遍歷數不超過k*/

④ while(|σL|+Sum

/*根據路徑步值來遍歷節點*/

⑤ for(Vi∈σL)

/*頂點加入集合S*/

⑥ insertTo(S，Vi)；

/*調用OpcWeiDist 算法*/

⑦ OpcWeiDist；

⑧ visited=true;

⑨ end for

⑩ /*增加路徑步*/

/*S按照距離頂點進行排序*/

算法2OpcWeiDist

輸入：包含Vi，V0的帶權不確定子圖g

輸出：dW×P(V0, Vi)

/*計算路徑步*/

① P=L(V0, Vi)

/*根據頂點間路徑步值不同情況計算*/

② switch(P)

/*頂點直接相連*/

③ case 1:

/*頂點間接相連*/

⑤ case n>1:

/*遞歸調用OpcWeiDist 算法，L(Vk,Vi)=1*/

/*頂點不相連*/

⑦ case ∞：

⑧ dW×P(V0, Vi)=∞；

⑨ end switch

⑩ Output(dW×P(V0, Vi));

KNN查詢算法主要包括兩個算法，SubDistK算法旨在給定帶權不確定圖，查找滿足要求的k個節點。期間調用OpcWeiDist算法，計算被訪問節點與查詢源點的ProWeiDist距離。 SubDistK算法的時間復雜度為O(N3)。空間復雜度為O(N)，OpcWeiDist算法的時間復雜度為O(N2)。

2.4實例分析

社交網絡中用戶關系網可以用帶權不確定圖表示：每一位用戶構成圖中的一個頂點；用戶間的好友關系對應頂點之間的邊，好友關系是相互的，所以邊不帶有方向；根據用戶的個人信息如職業、興趣愛好等不確定數據得出的好友關系成立的可能性表示為邊的概率值；把用戶在一段時間內相互關注和聯系的次數作為邊的權重值。圖2是一張社交網絡用戶關系圖，P表示用戶間好友關系存在的概率，W表示用戶在一個月內聯絡的次數。需要查找與用戶A親密度最高的4個用戶。

圖2　社交網絡用戶關系圖

根據查詢算法，與點A路徑步為1的節點為B、C，構成第一個源頂點層σ1,dW×P(A,B)=2.60，dW×P(A,C)=2.05；由于|σ1|=2，小于查找目標數，因此擴大路徑步值，遍歷第二個源定點層中的節點D、F、L，dW×P(B，F)=1.49，dW×P(B，L)=2.09，dW×P(C，F)=3.50，dW×P(C，D)=1.29，經過兩層遍歷，中間集合S已經有5個元素，超過了查詢參數k，因此終止遍歷過程，獲得一張帶權不確定子圖，如圖3所示。計算集合中每個節點與源點的距離dW×P(A，B)=2.60，dW×P(A，C)=2.05，dW×P(A，D)=2.64，dW×P(A，F)有兩個值，分別為7.18和3.87，取最小值3.87。dW×P(A，L)=5.43，選取距離值最小的四個節點，依次是C，B，D，F。因此得出結論與用戶A關系最近的用戶為用戶C，B，D，F。

圖3　社交網絡用戶關系子圖

3算法優化

本節從空間復雜度和時間復雜度兩個方面對算法進行優化，提出精簡帶權不確定子圖，用實例進行優化分析，并給出優化后的算法。

3.1優化方法

在空間復雜度方面，帶權不確定子圖用來存儲全部頂點和遍歷經過的邊，節約了其他無用邊的存儲空間。但是在復雜網絡中，頂點的數量龐大。依據SubDistK算法，遍歷過程中沒有經過的節點沒有成為查詢目標的可能性，因此可以在子圖中刪除這些節點，極大地降低算法的空間復雜度。圖3的所有節點中，只有B、C、D、F、L是候選節點，其他節點都可以省去，形成精簡帶權不確定子圖，如圖4所示。

圖4　社交網絡用戶關系精簡子圖

在時間復雜度方面，由于查詢執行時間主要在計算子圖中頂點與查詢源點的ProWeiDist距離，圖的節點和邊都比較復雜，會出現多個節點共用一條邊的情況。在現實生活中，一個人成為多人的中間好友的情況是經常存在的。在距離計算中，減少遍歷過程中重復邊的計算，簡化計算過程，有利于降低算法的時間復雜度。

圖4中節點L、F在與A點的連接路徑中共用了A-B邊，節點D、F在與A點的連接路徑中共用了A-C邊。在計算L與A點的距離計算過程中，可以減少重復計算A-B邊距離的步驟。同樣dW×P(A,D)與dW×P(A,F)也可以利用之前計算得到的dW×P(A,C)，在第二部分的算法示例中，第一層遍歷的邊的最可能權重距離在第二層遍歷中都會用到，在應用式(1)時可以利用。

3.2優化算法

算法3ImpSubDistK

輸入：帶權不確定圖G=(V，E，P，W)

查詢源點V0∈V

參數k≤|E|

輸出：結果集合Sk

/*初始化精簡子圖g*和相鄰點距離集合δ */

① g*=(V*，E*，P*，W*)；V*= ?，E*=?；δ =?；

② L=0，S=?;

③ L++; visited=false; Sum=0;

④ while(|σL|+Sum

⑤ for(Vi∈σL)

⑥ if(L==1)

⑦ 應用式(1);得dW*P(V0,Vi);

⑧ else if

⑨ ?Vk(Vk∈σL-1&&L(Vk,Vi)==1)

/*獲得相鄰邊距離并導入到距離集合中*/

⑩ dW×P(Vk,Vi)，insertTo(δ，dW×P(Vk,Vi));

/*把已訪問的節點信息加入到精簡子圖中*/

ImpSubDistK算法是在SubDistK算法的基礎上進行優化，節省存儲空間，提高查詢效率。改進后的算法空間復雜度為O(log2N)，時間復雜度為為O(N)。

4實驗

實驗部分利用社交網絡真實數據構建帶權不確定圖，進行多組實驗，從三個方面驗證算法的準確度和效率，并分析實驗結果。

4.1實驗環境

為了證明SubDistK算法在GrapKDist查詢過程中的準確性和高效性，本文以社交網絡中用戶關系網絡為帶權不確定圖原型，設計多組對比實驗，實驗采用ego-Facebook社交網絡數據。實驗算法代碼采用C++編程語言編寫，程序運行在3.2 GHz的雙核處理器上，實驗平臺為Win7 64位系統，4 GB內存。

實驗數據為Facebook社交圈，包含4093個節點，88 234條邊。該無向圖出于隱私保護經過匿名化處理，用戶ID用新的值代替，用戶間的個人特征也經過預處理。例如“政治派別=民主黨”也統一標識為“政治派別=A黨”，概率描述用戶間好友關系成立的可能性，在0~1之間；權重為兩個用戶一個月之內彼此在對方主頁進行關注和留言的次數總和。

4.2實驗方法

實驗對比主要從3個方面來驗證GrapKDist查詢的準確率和效率：目標頂點數與查詢中間候選集合的比例隨參數k的變化、查詢遍歷的頂點數占總頂點數的比例隨參數k的變化、查詢執行時間隨參數k的變化。

由于在查詢過程中，遍歷過的頂點會形成一個精簡帶權不確定子圖，直到子圖里的頂點數量超過要查詢的頂點數k。并且目標頂點包含在這個中間候選集合中，如果候選集合的元素越多，在里面挑選目標對象的準確性會越高，目標對象被查詢遺漏的可能性也就越低。這樣，目標頂點數k與中間候選集合元素個數的比例可以衡量算法的準確度。如果，這個比例在隨著參數k的變化一直保持在一個預期的閾值之下，那么說明查詢算法的準確率達到我們的期望。查詢過程中并不會遍歷圖中所有頂點，遍歷的頂點越多，要計算的ProWeiDist距離的次數就越多；算法執行時間就越長，所耗費的計算開銷就越大；另外查詢如果能夠以規模較小的中間候選集合就能找到目標頂點，就省去了遍歷無效頂點的過程，減少了無效距離的計算，因此查詢執行時間、查詢頂點數、與查詢頂點數占總頂點數的比例，這三個指標可以衡量查詢算法的效率。

4.3結果分析

實驗一只有參數k變化時，目標頂點數與中間候選集合元素個數的比例變化。

實驗設定帶權不確定圖的規模不變，逐漸擴大查詢目標個數k，從最初的查找4個對象頂點到最終的110個對象，前5次每次增加為4，后9次每次增加為10，總共測得14組比例數據，比例變化如圖5所示。從圖中我們可以得知，在目標頂點個數比較少的時候，遍歷的層次沒有變化，候選集合中包含了要查詢的目標頂點，集合中的無效頂點逐漸減少，所以前期比例呈線性增長。當k逐漸增加時，以前遍歷的層無法容納所有的目標頂點，必須再向外訪問新的頂點層，中間候選集合中的無效頂點瞬間增多，所以比例會突然出現比較大的下降。之后中間集合又會保持穩定，隨著k增加，無效頂點較少，比例增加。整個過程中比例的變化趨勢呈現鋸齒狀，線性增加然后大幅度下降再增加，周而復始。從實驗結果得出，算法的準確率會不斷變化，在k剛剛超出候選集合的頂點數即訪問新一層時的準確率最高。

圖5　隨k增加的目標頂點與候選集合的比例

實驗二只有參數k變化時，算法遍歷頂點數以及與總頂點數比例的變化。

該實驗設定圖頂點總數不變，當逐漸增加查詢目標數k時，計算算法遍歷過的頂點數占總頂點數的比例。結果如圖6所示，隨著參數k的增加，訪問的層次數也會增加，因此遍歷的頂點數增加。比例線呈現“階梯”狀，這是因為在查詢中，會以源點為“中心”向外層次性遍歷頂點。在第一個頂點層中，雖然參數k增加了，但是訪問的層次卻依然保持不變，所以遍歷的頂點數沒有變化。隨著k的進一步增加到16，訪問層次擴大，中間候選集合的規模變大，所以遍歷頂點數會進一步增多。從圖中我們可以看到，剛開始時，頂點數比例值保持在一個非常低的水平，這是由于開始階段查詢目標數少，并且總頂點數量大。中間一段過程中，比例的增長相對平緩，并且低于0.1，當k增加到110時，比例也不會超過0.055。說明在執行算法查詢過程中，從訪問頂點數比例來看，算法效率都保持在一個非常好的效果。

圖6　帶權不確定圖中訪問頂點占總頂點數的比例

實驗三只有參數k變化時，算法執行時間的變化。

查詢的執行時間集中于頂點的遍歷和ProWeiDist距離的計算方面上。而遍歷的頂點數比例隨參數k的變化在實驗二已經得出。頂點之間距離的計算時間也與頂點數有關系。因此查詢執行時間隨參數值k的變化趨勢會和頂點比例變化有聯動效果。實驗結果如圖7所示，曲線為算法優化前后的執行時間，當參數k在16以內時，形成的帶權不確定子圖所含的邊比較少，是一個稀疏圖，執行時間因此相差不大。k增加時，隨著遍歷新的頂點層時，訪問頂點數突然增多，需要進行的距離計算會大大增加，時間曲線有比較明顯的增大。在同一層遍歷頂點時，雖然增加k，但是時間增長平緩。當進一步增加查詢目標數時，曲線又會有一個比較大的提高。當k數值增加到110以后，新訪問的層所包含的頂點數量巨大，所包含的邊非常多，形成了一個規模很大的帶權不確定子圖，因此執行時間有大幅度的增長。從實驗結果得出，SubDistK算法在k在100以下時的運算時間比較小，且優化后的算法比優化前執行時間更短。

圖7　SubDistK算法隨參數k變化的執行時間

5結語

本文針對復雜網絡中同時含有概率和權重的數據查詢問題，通過帶權不確定圖對數據進行建模，定義了 GrapKDist查詢，提出了SubDistK算法，通過三組實驗證明了算法的有效性，解決了帶權不確定圖上的K最近鄰查詢問題。不足在于算法在k值在大于100時效率有所下降，這也是今后的研究方向。

參考文獻

[1] Qiao Shaojie,Li Tianrui,Yang Yan.Managing uncertainty in web-based social networks[J].Intertional Journal of Uncertianty,Fuzziness and Knowledge-Based System,2012,20(1):147-158.

[2] Zhu Fangzhou,Li Guohui,Zhao Xiaosong,et al.Probabilistic nearest neighbor queries of uncertain data via wireless data broadcast[J].Peer-to-Peer Networking and Applications,2013,6(4):363-379.

[3] Lima D M,Rodrigues J F.DeGraph-based relational data visualization[C]//Proceedings of the International Conference on Information Visualisation,2013.

[4] Wang Yijie,Li Xiaoyong,Qi Yafei,et al.Uncertain data queries Technologies[J].Journal of Computer Research and Development,2012,49(7):1460-1466.

[5] Asthana S,King O D,Gibbons F D,et al.Predicting protein complex membership using probabilistic network reliability[J].Genome Research,2004,14(3):1170-1175.

[6] Wang D Z,Michelakis E,Garofalakis M,et al.Bayesstore:managing large uncertain data repositories with probabilistic graphical models[J].Proc of the VLDB Endowment,2008,1(1):340-351.

[7] Liben-Nowell D,Kleinberg J.The link prediction problem for social networks[J].Journal of the American Society for Information Science and Technology,2007,58(7):1019-1031.

[8] Zhang Haijie,Jiang Shouxu,Zou Zhaonian.An efficient algorithm for top-k proximity query on uncertain graphs[J].Chinese Journal of Computers,2011,34(10):145-156.

[9] Zhang Shuo,Gao Hong,Li Jianzhong,et al.Efficient query processing on uncertain graph databaes[J].Chinese Journal of Computers,2009,23(10):2066-2079.

[10] Huang Jianhua,Ding Jianrui,Liu Jiafeng,et al.Citation-knn algorithm based on locally-weighting[J].Journal of Electronics and Information Technology,2013,35(3):627-632.

[11] Zhang Shichao.Nearest neighbor selection for iteratively knn imputation[J].Journal of System and Software,2012,85(11):2541-2552.

[12] Jiang Liangxiao,Cai Zhihua,Wang Dianhong.Bayesian citation-knn with distance weighting[J].International Journal of Machine Learning and Cybernetics,2014,5(2):193-199.

[13] Potamias M,Bonchi F,Gionis A,et al.k-nearest neighbors in uncertain graphs[J].Proc of the VLDB Endowment,2010,3(1):997-1008.

[14] Zhang Yinglong,Li Cuiping,Chen Hong,et al.K-nearest neighbors in uncertain graph[J].Journal of Computer Research and Development,2011,48(10):1850-1858.

[15] Zhang Xu,He Xiangnan,Jin Cheqing,et al.Processing k-nearest neighbors query over uncertain graphs[J].Journal of Computer Research and Development,2010,3(1):997-1008.

[16] Sun Yongjiao,Dong Han,Yuan Ye,et al.Knn queries method on uncertain data over P2P networks[J].Journal of Northeastern University,2012,33(5):632-635.

[17] Bekales G,Soliman M A,Ilyas I F.Efficient search for the top-k probable nearest neighbors in uncertain databases[J].Proc of the VLDB Endowment,2008,1(1):326-339.

[18] Kriegel H P,Kunath P,Renz M.Probabilistic nearest-neighbor query on uncertain objects[C]//Proc of DASFAA.Berlin:Springer,2007:809-824.

[19] Lian X,Chen L.Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data[J].The VLDB Journal,2009,18(3):787-808.

[20] Cheng R,Chen L,Chen J,et al.evaluating probability threshold k-nearest-neighbor queries over uncertain data[C]//Proc of Int on Extending Database Technology:Advances in Database Technology(EDBT).New York: ACM,2009:672-683.

中圖分類號TP311

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.050

收稿日期：2014-06-26。國家自然科學基金項目(61272098)。黃冬梅，教授，主研領域：海洋大數據，WebGis等。鄧斌，碩士生。趙丹楓，講師。