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

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

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

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

DOI：10.15938/j.jhust.2019.03.005

中圖分類號(hào)： TP311

文獻(xiàn)標(biāo)志碼： A

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

已有的組最近鄰查詢研究方法中，針對(duì)移動(dòng)對(duì)象本身的不確定性和障礙空間上的研究有所不足，且現(xiàn)有的kNN查詢大都只查詢要求的k個(gè)對(duì)象，而實(shí)際上只要在第k個(gè)最近鄰的相同范圍內(nèi)，可能會(huì)有大于等于k個(gè)對(duì)象。為了解決這些問題，進(jìn)一步提高查詢性能，本文提出了處理障礙空間中不確定對(duì)象的組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）查詢的定義。在本文中，任意兩個(gè)可見點(diǎn)之間的距離均采用歐幾里德度量方法計(jì)算，兩點(diǎn)間的可視距離用dist_euc（）表示，障礙距離均用dist_o（）表示。

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

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

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

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

2.1 集總障礙距離計(jì)算方法

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

算法1給出了集總障礙距離計(jì)算方法。算法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）中，首先計(jì)算數(shù)據(jù)點(diǎn)p和每個(gè)查詢點(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不相交的障礙物，同時(shí)將查詢點(diǎn)暫存在集合LQ中，障礙距離需要重新計(jì)算。只有當(dāng)p和q之間的最短路徑與通過增量障礙物檢索獲取的任何障礙物相交時(shí)，才需要重新計(jì)算數(shù)據(jù)點(diǎn)p和查詢點(diǎn)q之間的障礙距離，可視圖中的障礙距離采用Dijkstra算法進(jìn)行計(jì)算。在過濾掉不必要的障礙物之后，算法使用新障礙物更新局部可視圖，并且重新計(jì)算p和所有查詢點(diǎn)q∈LQ之間的障礙距離。重復(fù)該過程直到最短路徑上沒有新的障礙物或者LQ為空。

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

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

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

2.2.1 空間修剪方法

本文所提出的空間修剪方法主要思路：只要查詢對(duì)象最小集總障礙距離下限大于等于給定最小集總障礙距離上限，該對(duì)象就不屬于候選查詢對(duì)象。假設(shè)對(duì)象p具有所有數(shù)據(jù)對(duì)象中的最小集總障礙距離上限UB_adist_o（p，Q）。對(duì)于任何數(shù)據(jù)對(duì)象p，只要它保持LB_adist_o（p′，Q） ≥LB_adist_o（p′，Q）≥UB_adist_o（p，Q），就可修剪掉對(duì)象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}，新加入對(duì)象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′）中，首先判斷新加入對(duì)象的預(yù)期概率是否滿足概率閾值α。若不滿足，該對(duì)象不需要再檢索;若滿足，則進(jìn)一步將該對(duì)象到查詢點(diǎn)集的障礙集總距離的下界與候選集中集總障礙距離的上界相比較，若是大于，則該對(duì)象也不需要再檢索，否則，把該對(duì)象加入候選集中。

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

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

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

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

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

算法3 PruInterEnt（S）

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

輸出：Q的PGNNs的一個(gè)集合S

begin

S←，best_adist_o=+∞，H←;

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

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

while H≠Φ do

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

if e是一個(gè)葉結(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中;

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

return S

end

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

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

輸入：基于移動(dòng)數(shù)據(jù)庫構(gòu)建的R樹，查詢點(diǎn)集Q={q1，q2，…，qn}，查詢對(duì)象集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的時(shí)間復(fù)雜度為O（|G|×log|G|×n）;執(zhí)行算法2的時(shí)間復(fù)雜度為O（n）;執(zhí)行算法3的時(shí)間復(fù)雜度為O（log|T|）;執(zhí)行for循環(huán)的時(shí)間復(fù)雜度為O（n）。因此該算法的時(shí)間復(fù)雜度為O（|G|×log|G|×n+ 2n+log|T|）。

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

4 結(jié) 論

由于移動(dòng)數(shù)據(jù)對(duì)象本身固有的不確定性，對(duì)不確定數(shù)據(jù)的組k最近鄰查詢處理變得越來越重要。本文著重研究了障礙空間中不確定對(duì)象的組k最近鄰查詢方法。給出了集總障礙距離的計(jì)算方法、空間修剪方法、R樹中間結(jié)點(diǎn)修剪和最終精煉查詢方法。本文方法集成有效的修剪策略以便于減少POkGNN的搜索空間。實(shí)驗(yàn)結(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] 陳舒，蔣志會(huì)，陸恒，等. 路網(wǎng)環(huán)境中關(guān)于模糊組最近鄰問題的研究[J]. 計(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ì)算機(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é)報(bào)，2013，18（6）：58.

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

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

（編輯：溫澤宇）