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

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

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

DOI：10.15938/j.jhust.2019.03.005

中圖分類號： TP311

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

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

1 基本定義

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

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

最短路徑查詢基于可視圖進(jìn)行?？梢晥D中的節(jié)點(diǎn)由所有障礙物的頂點(diǎn)和點(diǎn)q、p組成，可視圖的邊由任意兩可視點(diǎn)的連線構(gòu)成。

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

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

2.1 集總障礙距離計算方法

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

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

算法1 Compadist_o（p，Q）

輸入：查詢點(diǎn)集Q={q1，q2，…，qn}，數(shù)據(jù)點(diǎn)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）中，首先計算數(shù)據(jù)點(diǎn)p和每個查詢點(diǎn)q∈Q之間的單獨(dú)歐幾里德距離，并將它們分配為p和q∈Q之間的初始障礙距離。接下來算法找到從單獨(dú)的障礙距離得到的最大障礙距離作為dmax，然后用單調(diào)遞增函數(shù)檢索dmax距離內(nèi)的所有障礙物。然而，在檢索障礙物之后，算法將過濾掉與數(shù)據(jù)點(diǎn)p和查詢點(diǎn)q∈Q之間的任何最短路徑SPp，q不相交的障礙物，同時將查詢點(diǎn)暫存在集合LQ中，障礙距離需要重新計算。只有當(dāng)p和q之間的最短路徑與通過增量障礙物檢索獲取的任何障礙物相交時，才需要重新計算數(shù)據(jù)點(diǎn)p和查詢點(diǎn)q之間的障礙距離，可視圖中的障礙距離采用Dijkstra算法進(jìn)行計算。在過濾掉不必要的障礙物之后，算法使用新障礙物更新局部可視圖，并且重新計算p和所有查詢點(diǎn)q∈LQ之間的障礙距離。重復(fù)該過程直到最短路徑上沒有新的障礙物或者LQ為空。

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

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

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

2.2.1 空間修剪方法

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

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

算法2 SpatialPru（P′）

輸入：查詢點(diǎn)集Q={q1，q2，…，qn}，數(shù)據(jù)點(diǎn)集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′）中，首先判斷新加入對象的預(yù)期概率是否滿足概率閾值α。若不滿足，該對象不需要再檢索;若滿足，則進(jìn)一步將該對象到查詢點(diǎn)集的障礙集總距離的下界與候選集中集總障礙距離的上界相比較，若是大于，則該對象也不需要再檢索，否則，把該對象加入候選集中。

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

2.2.2 修剪R樹中間結(jié)點(diǎn)

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

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

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

算法3 PruInterEnt（S）

輸入：基于移動數(shù)據(jù)庫構(gòu)建的R樹，查詢點(diǎn)集Q={q1，q2，…，qn}，概率閾值α∈（0，1]

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

begin

S←，best_adist_o=+∞，H←;

從R樹的根結(jié)點(diǎn)開始進(jìn)行遍歷;

將R樹的根結(jié)點(diǎn)插入到H中;

while H≠Φ do

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

if e是一個葉結(jié)點(diǎn)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中;

通過計算不等式中的預(yù)期概率來細(xì)化S中的候選對象;

return S

end

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

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

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

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

算法4 PkOGNN（Q，Pk）

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

輸出：PkOGNN（Q，Pk）

begin

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

S←SpatialPru（P′） ;//調(diào)用算法2獲得候選集S

best_adist_o←PruInterEnt（S） ; //調(diào)用算法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）執(zhí)行算法1的時間復(fù)雜度為O（|G|×log|G|×n）;執(zhí)行算法2的時間復(fù)雜度為O（n）;執(zhí)行算法3的時間復(fù)雜度為O（log|T|）;執(zhí)行for循環(huán)的時間復(fù)雜度為O（n）。因此該算法的時間復(fù)雜度為O（|G|×log|G|×n+ 2n+log|T|）。

3 實驗結(jié)果與分析

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

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

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

4 結(jié) 論

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

參 考 文 獻(xiàn)：

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

[2] 陳舒，蔣志會，陸恒，等. 路網(wǎng)環(huán)境中關(guān)于模糊組最近鄰問題的研究[J]. 計算機(jī)應(yīng)用研究， 2016，33（2） ：333.

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

[4] 劉曉樂，李博.隱私保護(hù)下的組最近鄰查詢算法研究[J]. 計算機(jī)應(yīng)用與軟件. 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].哈爾濱理工大學(xué)學(xué)報，2013，18（6）：58.

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

[11]李傳文，谷峪，李芳芳，等. 一種障礙空間中不確定對象的連續(xù)最近鄰查詢方法[J].計算機(jī)學(xué)報，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.

（編輯：溫澤宇）