障礙空間中不確定對象的組k最近鄰查詢方法

萬靜　唐貝貝　孫健　何云斌　李松

摘 要：針對障礙空間中不確定對象的組k最近鄰查詢問題，提出了PkOGNN（probabilistic k obstructed group nearest neighbor query）查詢方法。PkOGNN查詢方法主要包括4個子算法：Compadist_o（），SpatialPru（），PruInterEnt（）和PkOGNN（），這些子算法分別是集總障礙距離的計算方法、空間修剪方法、根據空間修剪方法進行R樹中間結點修剪、最終精煉查詢方法。所提PkOGNN查詢方法通過集成有效的修剪策略以便減少PkOGNN的搜索空間，得到正確的kGNNs。理論研究和實驗結果表明，所提方法具有較好的性能。

關鍵詞：R樹;組最近鄰查詢;不確定性;可視性;障礙距離

DOI：10.15938/j.jhust.2019.03.005

中圖分類號： TP311

文獻標志碼： A

文章編號： 1007-2683（2019）03-0029-06

Abstract：To deal with the problem of group knearest neighbor query method for uncertainty data in obstructed spaces， this paper presents the method of the PkOGNN（probabilistic k obstructed group nearest neighbor）query. The PkOGNN query method mainly includes four subalgorithms： Compadist_o（），SpatialPru（），PruInterEnt（） and PkOGNN（）， These algorithms are respectively the calculation of the aggregate obstructed distance， the spatial pruning method， the pruning of the Rtree intermediate items according to the spatial pruning method， the final refined query method. It integrates the effective pruning methods to reduce the search space of PkOGNN and get the correct kGNNs. The theoretical research and experimental results show that the proposed method has good efficiency.

Keywords：Rtree; group nearest neighbor query; uncertainty; visibility; obstructed distance

0 引 言

組最近鄰[1-2]（GNN，group nearest neighbor）查詢是一項重要的信息查詢服務類型。通過組最近鄰查詢可以確定位于一個城市不同區域的一組朋友，使他們到達指定的餐館、購物中心或電影院的公共興趣點（POI）的距離和（集總距離）最小化或者最大化。從而使得組成員能夠在最短的可能時間內在POI處相遇。國內外對組最近鄰查詢進行了一些重要研究。其中，文[1]和文[2]給出了路網中的組最近鄰查詢方法。文[3]給出了歐幾里德空間中的組最近鄰查詢方法。文[4]給出了隱私保護下的組最近鄰查詢方法。Gao等[5]提出了障礙空間下的CONN（continuous obstructed nearest neighbor）查詢方法。Sultana等[6]提出了障礙空間中的組最近鄰OGNN（obstructed group nearest neighbor）查詢方法。然而，已有的方法沒有考慮到查詢對象本身的不確定性。為了保護基于服務的位置隱私性，不確定性被加入到用戶的位置信息中[7]。如文[8]給出了基于位置不確定性的k最近鄰（kNNs）查詢方法;文[9]提出了基于不確定Voronoi圖的概率性查詢方法。

已有的組最近鄰查詢研究方法中，針對移動對象本身的不確定性和障礙空間上的研究有所不足，且現有的kNN查詢大都只查詢要求的k個對象，而實際上只要在第k個最近鄰的相同范圍內，可能會有大于等于k個對象。為了解決這些問題，進一步提高查詢性能，本文提出了處理障礙空間中不確定對象的組k最近鄰查詢方法。

1 基本定義

基于點與點的可視性[10] ，最短障礙距離[11]，GNN查詢[12]，kOGNN查詢[13]，PGNN查詢[14]的定義，本小節進一步給出了PkOGNN（probabilistic k obstructed group nearest neighbor query）查詢的定義。在本文中，任意兩個可見點之間的距離均采用歐幾里德度量方法計算，兩點間的可視距離用dist_euc（）表示，障礙距離均用dist_o（）表示。

定義1 （POkGNN查詢）給定一個移動對象數據庫D，一組查詢點集合Q={q1，q2，…，qn}，一組障礙物集合O={o1，o2，…，on}，和一個用戶給定的概率閾值α∈（0，1]。 POkGNN查詢就是檢索一組數據對象p∈D，該集合是具有大于α的概率的查詢集合Q的GNN。

最短路徑查詢基于可視圖進行?？梢晥D中的節點由所有障礙物的頂點和點q、p組成，可視圖的邊由任意兩可視點的連線構成。

2 障礙空間中不確定對象的組k最近鄰查詢

本文中，移動對象o的可能區域Ro（t）隨著時間在不斷移動，Ro（t）的模型是一個圓環，內環對應查詢對象以最小速度運動在數據庫下次更新之前所達到的位置;外環對應查詢對象以最大速度運動在數據庫下次更新之前所達到的位置，運動方向是圓環內的任意方向。

2.1 集總障礙距離計算方法

在進行計算時，只要被檢索的障礙物與查詢對象p和Q之間的集總障礙距離不相關，則就不需要檢索該障礙物，即不需要把該障礙物加入可視圖中。

算法1給出了集總障礙距離計算方法。算法1的輸入是一組查詢點集Q={q1，q2，…，qn}，數據點集中的任一點p∈P={p1，p2，…，pm}，障礙物R樹Tobs和局部可視圖LVG。算法的輸出是任一數據點p∈P和用戶組之間的集總障礙距離adist_o（p，Q）。

算法1 Compadist_o（p，Q）

輸入：查詢點集Q={q1，q2，…，qn}，數據點p，障礙物R樹Tobs，局部可視圖LVG

輸出：集總障礙距離adist_o（p，Q）

begin

for q∈Q do

dist_o（p，qi）←dist_euc（p，qi）;

O←;

repeat

dmax←max1≤i≤n dist_o（p，qi） ;

if dist_o（p，qi）≤dmax

{O} =fdist_o （o，Q） ;

foro∈O do

forq∈Q do

if o與p、q之間的最短路徑SPp，q相交then

q∈LQ;

o∈LVG;

forq∈LQ do

dist_o（p，q）=Dijkstra（LVG，q，p）;

until LQ=;

adist_o（p，Q）=fa（i=1，2，…，n）（dist_o（p，qi）） ;

return adist_o（p，Q） ;

end

算法Compadist_o（p，Q）中，首先計算數據點p和每個查詢點q∈Q之間的單獨歐幾里德距離，并將它們分配為p和q∈Q之間的初始障礙距離。接下來算法找到從單獨的障礙距離得到的最大障礙距離作為dmax，然后用單調遞增函數檢索dmax距離內的所有障礙物。然而，在檢索障礙物之后，算法將過濾掉與數據點p和查詢點q∈Q之間的任何最短路徑SPp，q不相交的障礙物，同時將查詢點暫存在集合LQ中，障礙距離需要重新計算。只有當p和q之間的最短路徑與通過增量障礙物檢索獲取的任何障礙物相交時，才需要重新計算數據點p和查詢點q之間的障礙距離，可視圖中的障礙距離采用Dijkstra算法進行計算。在過濾掉不必要的障礙物之后，算法使用新障礙物更新局部可視圖，并且重新計算p和所有查詢點q∈LQ之間的障礙距離。重復該過程直到最短路徑上沒有新的障礙物或者LQ為空。

算法Compadist_o（p，Q）的執行時間主要是repeat循環和Dijkstra算法的執行時間。其中repeat循環的時間復雜度為O（n），而Dijkstra算法的時間復雜度為（|G|×log|G|）。因此，Compadist_o（p，Q）算法的時間復雜度為O（|G|×log|G|×n）。

2.2 概率障礙組最近鄰查詢剪枝方法

概率組最近鄰（PGNN）查詢檢索一組移動對象，使得它們的GNN的概率大于用戶指定的概率閾值α，其中α∈（0，1]。假設D中的每個數據對象可以由不確定區域UR（r）表示，其中q（q∈Q）位于位置q0∈UR（r），其概率為pdf（q0）≥0（如果q0不在UR（r）中，則pdf（q0）=0），其中pdf（.）是對象q的概率密度函數（pdf）。

2.2.1 空間修剪方法

本文所提出的空間修剪方法主要思路：只要查詢對象最小集總障礙距離下限大于等于給定最小集總障礙距離上限，該對象就不屬于候選查詢對象。假設對象p具有所有數據對象中的最小集總障礙距離上限UB_adist_o（p，Q）。對于任何數據對象p，只要它保持LB_adist_o（p′，Q） ≥LB_adist_o（p′，Q）≥UB_adist_o（p，Q），就可修剪掉對象p′，其中LB_adist_o（p′，Q）是從p′到Q的集總障礙距離的下限。

基于以上討論，本節給出空間修剪方法如算法2所示。

算法2 SpatialPru（P′）

輸入：查詢點集Q={q1，q2，…，qn}，數據點集P={p1，p2，…，pm}，新加入對象p，概率閾值α∈（0，1]，障礙物R樹Tobs，局部可視圖LVG

輸出：candidates（P′）

begin

forp∈P do

if pdf（p） ∈α then

UB_adist_o（p，Q）←max（adist_o（p，Q）） ;

while P′≠ do

if LB_adist_o（p′，Q）≥UB_adist_o（p，Q） then

P′←P′-{p′};

else P′←P′+{p′};

forpi∈P′ do

if pdf（pi）∈α then

if LB_adist_o（pi，Q）≥UB_adist_o（p，Q） then

P′←P′-{pi};

return candidates（P′） ;

end

算法SpatialPru（P′）中，首先判斷新加入對象的預期概率是否滿足概率閾值α。若不滿足，該對象不需要再檢索;若滿足，則進一步將該對象到查詢點集的障礙集總距離的下界與候選集中集總障礙距離的上界相比較，若是大于，則該對象也不需要再檢索，否則，把該對象加入候選集中。

算法SpatialPru（P′）中主要是while循環，假設P中有n個對象，那么while循環所需的時間為O（n）。所以算法的時間復雜度為O（n）。

2.2.2 修剪R樹中間結點

本小節進一步研究在R樹中修剪中間結點的方法。在逐點修剪過程中，給定所有對象中從p到Q的最小上界UB_adist_o（p，Q），如果 UB_adist_o（p，Q） ≤LB_adist_o（p′，Q），則任何對象p′∈D可以被修剪，其中Q是由PGNN查詢指定的n個查詢點的集合。類似的，在包含許多不確定對象的中間結點e的情況下，只要結點e中的任何對象h滿足條件UB_adist_o（p，Q）≤LB_adist_o（h，Q），則整個結點e就可以被安全的修剪掉。然而，由于結點e中的對象h的確切位置未知而未訪問其對應的子樹，則放寬修剪條件，即如果UB_adist_o（p，Q）≤LB_adist_o（e，Q）成立，則R樹中的任何中間結點e都

可以被刪除，其中對象p在所有對象中具有最小的UB_adist_o（p，Q），LB_adist_o（e，Q）是從任何點h∈e到查詢集Q的最小可能聚合距離。

基于以上討論，本節給出空間修剪算法如算法3所示。

算法3 PruInterEnt（S）

輸入：基于移動數據庫構建的R樹，查詢點集Q={q1，q2，…，qn}，概率閾值α∈（0，1]

輸出：Q的PGNNs的一個集合S

begin

S←，best_adist_o=+∞，H←;

從R樹的根結點開始進行遍歷;

將R樹的根結點插入到H中;

while H≠Φ do

將H中的第一個元素（e，key）出棧;

if e是一個葉結點then

forh∈e do

if LB_adist_o（h，Q） ≤best_adist_o then

h∈S;

best_adist_o=min{ UB_adist_o（h，Q），best_adist_o};

else

forei∈e do

if LB_adist_oMBR（ei，Q）≤best_adist_o then

if LB_adist_o（ei，Q） ≤best_adist_o

then

將（ei， LB_adist_o（ei，Q））插入到H中;

else

forei∈e do

將（ei，LB_adist_o（ei，Q））插入到H中;

通過計算不等式中的預期概率來細化S中的候選對象;

return S

end

算法PruInterEnt（S）中，首先遍歷R樹的根節點，并將R樹中未訪問的節點插入堆棧H中。算法假設初始集總障礙距離best_adist_o為+∞，對于小于該距離的任意元素（e，key），如果e是葉節點，且如果節點e中的任何對象h滿足條件LB_adist_o（h，Q）≤best_adist_o，那么集總障礙距離best_adist_o的下界需要更新為LB_adist_o（h，Q）的最小值，否則依次判定節點e中的對象ei是否滿足滿足條件LB_adist_o（ei，Q）≤best_adist_o，若滿足就把該元素插入堆棧H中。如果e是非葉節點，就把e中的元素依次插入堆棧H中，再重復以上方法進行判定。最后計算不等式中的預期概率來細化S中的候選對象。

算法PruInterEnt（S）的執行時間主要是遍歷Rs的時間，而遍歷一次R樹的時間復雜度為O（log|T|），因此算法PruInterEnt（S）的時間復雜度為O（log|T|）。

2.3 概率障礙組k最近鄰查詢

基于算法1，2，3，本節進一步給出了基于R樹的概率性障礙組k最近鄰查詢算法如算法4所示。其主要思想為： PruInterEnt（S）將一組查詢點集Q和概率閾值α作為輸入，并且通過最佳優先遍歷的方法遍歷R樹來返回一組PGNN集合。

算法4 PkOGNN（Q，Pk）

輸入：基于移動數據庫構建的R樹，查詢點集Q={q1，q2，…，qn}，查詢對象集P={p1，p2，…，pm}障礙物R樹Tobs，概率閾值α∈（0，1]

輸出：PkOGNN（Q，Pk）

begin

adist_o（p，Q）←Compadist_o（p，Q） ; //調用算法1獲得集總障礙距離

S←SpatialPru（P′） ;//調用算法2獲得候選集S

best_adist_o←PruInterEnt（S） ; //調用算法3獲得最佳集總障礙距離

forp∈S do

PkOGNN（Q）←{p1，p2，…，pk};

for i=1 to k do

if LB_adist_o（pi，Q） ≤best_adist_o then

best_adist_o_pk←

min{UB_adist_o（pi，Q），best_adist_o};

if LB_adist_o（p，Q）≥best_adist_o_pk then

Pk←Pk -{p};

return PkOGNN（Q，Pk）;

end

算法PkOGNN（Q，Pk）執行算法1的時間復雜度為O（|G|×log|G|×n）;執行算法2的時間復雜度為O（n）;執行算法3的時間復雜度為O（log|T|）;執行for循環的時間復雜度為O（n）。因此該算法的時間復雜度為O（|G|×log|G|×n+ 2n+log|T|）。

3 實驗結果與分析

本節所用的實驗數據集主要是合成的數據集合。實驗過程中，我們通過改變組的大小驗證所提算法的性能。實驗結果為算法執行100次的平均值，允許查詢點位于障礙物的邊界上，但不在障礙物內部。我們將實驗結果與文[13]所提算法（GBQM）中的組的大小對計算機性能的影響進行比較分析。為了便于比較，對實驗算法細節進行了局部調整。實驗運行環境為：1.70 GHz Intel CoreTM i5-3317U CPU、4GB RAM、Windows7操作系統。

圖1和圖2分別給出了相同組大小、不同聚合函數情況下兩種算法對查詢時間的影響。

由實驗可知，GBQM和POkGNN的性能都隨著組大小的增加而降低。這是因為組大小的增加使得障礙距離計算的數量增大，并且因此增加了從障礙物R樹中檢索更多障礙物的代價。對于SUM和MAX，由實驗可知，本文所提的POkGNN方法的性能優于GBQM方法。MAX比SUM的CPU時間和IO訪問更低，這是因為MAX的精確搜索區域比SUM小。

4 結 論

由于移動數據對象本身固有的不確定性，對不確定數據的組k最近鄰查詢處理變得越來越重要。本文著重研究了障礙空間中不確定對象的組k最近鄰查詢方法。給出了集總障礙距離的計算方法、空間修剪方法、R樹中間結點修剪和最終精煉查詢方法。本文方法集成有效的修剪策略以便于減少POkGNN的搜索空間。實驗結果表明所提方法具有較好的性能。未來的研究重點主要集中在受限不確定組k最近鄰查詢問題的研究方面。

參 考 文 獻：

[1] SUN W， CHEN C， ZHENG B， et al.Merged Aggregate Nearest Neighbor Query Processing in Road Networks[C]// CIKM， 2013：2243.

[2] 陳舒，蔣志會，陸恒，等. 路網環境中關于模糊組最近鄰問題的研究[J]. 計算機應用研究， 2016，33（2） ：333.

[3] HASHEM T， KULIK L， ZHANG R. Privacy Preserving Group Nearest Neighbor Queries[C]// EDBT， 2010：489.

[4] 劉曉樂，李博.隱私保護下的組最近鄰查詢算法研究[J]. 計算機應用與軟件. 2016，33（5）：302.

[5] GAO Yunjun， ZHENG Baihua. Continuous Obstructed Nearest Neighbor Queries in Spatial Databases[C]// Proceedings of the 28th ACM SIGMOD International Conference of Management of Data，2009，9（4）： 577.

[6] SULTANA N， HASHEM T， KULIK L. Group Nearest Neighbor Queries in the Presence of Obstacles[C]// International Conference on Advances in GIS，2014：481.

[7] MOKBEL MF， CHOW CY， AREF WG. The Newcasper： Query Processing for Location Services Without Compromising Privacy[C]// International Conference on Very Large Data Bases， 2009， 34（4）：763.

[8] HUANG YuanKo， CHEN ChaoChun， LEE Chiang. Continuous knearest Neighbor Query for Moving Objects with Uncertain Velocity[J]. Geoinformatica ，2009，13（1）： 1.

[9] 孫冬璞，郝曉紅，高爽，等. 概率可視最近鄰查詢算法[J].哈爾濱理工大學學報，2013，18（6）：58.

[10]SACK JUJR. Handbook of Computational Geometry [M]. Ottawa： Elsevier Science，2000：829.

[11]李傳文，谷峪，李芳芳，等. 一種障礙空間中不確定對象的連續最近鄰查詢方法[J].計算機學報，2010，33（8）：1359.

[12]PAPADIAS D， SHEN Qiongmao， TAO Yufei， et al. Group Nearest Neighbor Queries[C]//ICDE，2004，312.

[13]SULTANA Nusrat， HASHEM Tanzima， KULIK Lars. Group Nearest Neighbor Queries in the Presence of Obstacles[J].? International Conference on Advances in GIS， 2014：481.

[14]LIAN X， CHEN L. Probabilistic Group Nearest Neighbor Queries in Uncertain Databases[J]. IEEE Transactions on Knowledge & Data Engineering，2008， 20（6）：809.

（編輯：溫澤宇）