障碍空间中不确定对象的组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。

最短路径查询基于可视图进行。可视图中的节点由所有障碍物的顶点和点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.

（編辑：温泽宇）