障碍空间中基于voronoi图的k最近邻查询-张丽平.pdf

《障碍空间中基于voronoi图的k最近邻查询-张丽平.pdf》由会员分享，可在线阅读，更多相关《障碍空间中基于voronoi图的k最近邻查询-张丽平.pdf（6页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第43卷第5期2016年5月计算机科学Computer ScienceV0143 No5May 2016障碍空间中基于Voronoi图的k最近邻查询张丽平经海东李松崔环宇(哈尔滨理工大学计算机科学与技术学院 哈尔滨150080)摘 要 为了提升障碍空间中k最近邻查询的效率，研究了障碍空间中基于Voronoi图的k最近邻查询方法，提出了在障碍空间基于Voronoi图的kNNObs算法。该算法采用了两个过程：过滤过程和精炼过程。过滤过程主要是利用Voronoi图的过滤功能，较大程度地减少了被查询点的个数。精炼过程主要根据障碍距离和邻接生成点对候选集内对象进行第二次筛选。进一步给出了处理新增加点的A

2、DDkNN-Obs算法和处理删除点的DENkNN一0bs算法。实验表明该算法在处理障碍空间中的k最近邻问题时具有优势。关键词Voronoi图，k最近邻查询(kNN)，障碍空间，障碍距离中图法分类号TP31113 文献标识码A DOI 1011896jissn1002137X 20165032k Nearest Neighbor Query Based on Voronoi Diagram for Obstructed SpacesZHANG Li-ping JING Hai_dong LI Song CUI Huan-yu(school of Computer Science and Tech

3、nology，Harbin University of Science and Technology，Harbin 150080，China)Abstract In order to enhance the efficiency Of k nearest neighbor in obstructed spaces，k nearest neighbor query methodbased on Voronoi diagram in obstructed spaces was studied，and kNN-Obs algorithm based on Voronoi diagram in obs

4、tructed spaces was proposedThis algorithm adopts tWO processes：filtration and refinementFiltration mainly uses thefilter function of Voronoi diagram and largely reduces the number of query pointsRefinement mainly screens objectswithin the candidate set according to barrier distance and Voronoi neigh

5、borAnd further ADDkNN-Obs algorithm fornewly-added points and DENkNN-Obs algorithm for deleted points were givenThe experiment shows that the algorithm has advantages in dealing with the k nearest neighbor problem in obstructed spacesKeywords Voronoi diagram，k nearest neighbor query，Obstructed space

6、s，Obstructed distance1 引言Voronoi图是计算几何领域中的一个重要分支，Voronoi图的一些重要性质如近邻性质、最大空圆性质、控制范围性质等，使其在实际生产和科学研究领域受到了较多的关注。针对复杂的数据集，Voronoi图在查找最近点、求最大空圆、求行个点的凸包、求最小树等问题方面具有重要作用。此外，Voronoi图与其对偶图Delaunay三角剖分已被广泛地应用到几何形体重构、空间数据聚类、空间数据挖掘、图像处理、移动通信、模式识别、机器人运动规划、方向关系分析等领域r1。在GIS、卫星定位与遥感领域，Voronoi图可表达空间数据信息中的侧向邻近关系，并兼具矢量

7、和连续铺盖数据模型的基本特点，可以很好地管理空间数据，因此成为GIS等领域近年的研究热点之一23。随着移动设备和无线网络的广泛应用，移动对象的动态查询迅速发展。其中，最近邻查询成为空间数据库中的研究重点。最近邻查询的研究中大部分都是关于kNN查询以及连续kNN查询的算法4。7。国内在空间与时空对象最近邻查询处理技术方面的研究工作也取得了较为丰硕的成果。张丽平等人提出了Voronoi图的构建与受限区域内的最近邻查询方法8；袁培森、沙朝锋等人研究了一种基于学习的高维数据c一近似最近邻查询算法9；卢炎生等人提出了一种改进的基于BF的NN算法1叼；李松等人提出了动态受限区域内的单纯型连续近邻链查询方法

8、11|。但是以上算法都是基于理想的欧氏空间的。在障碍空间中，kNN查询能获取在障碍距离上k个距离查询点q最近的空间数据点。Gao等人12通过有效地分割对象行进的路径，提出了障碍空间内连续kNN查询优化方法，该算法的优点是查询速度较快，但是随着数据点的增加其查询的准确性会降低。Sarana Nutanong等1 3利用增量算法来处理障碍空间的最近邻问题，该算法的准确性高，但是在海量数据查询方面尚需进一步提升。Gao等1 4提出了一种基于Rtree的障碍空间反最近邻(RNN)查询处理方法，该方法不需要预计算，通过引入边界区域的概念对查询结果进行高效的剪枝。Li等到稿日期：20150318返修日期：

9、20150728 本文受国家自然科学基金资助项目(61370084)，黑龙江省自然科学基金资助项目(F201302)，黑龙江省教育厅科学技术研究项目(12541128，125312004)资助。张丽平(1976-)，女，硕士，副教授主要研究方向为数据结构和算法设计、数据库，E-mail：zhanglipin90730163com；经海东(1990-)，男，硕士生，主要研究方向为空间数据查询与处理、算法设计；李松(1977一)，男，博士，副教授，主要研究方向为数据库理论与技术、算法设计；崔环宇(1990一)，男，硕士生，主要研究方向为数据查询与分析。 174万方数据人Ll副提出了一种安全的基于区

10、域的方法来进行空间移动的kNN查询，该方法在一些情况下计算量较大。Wang等人口6提出了移动对象的持续可见k近邻查询。为了进一步提升查询性能，提出了一种改进的障碍空间中基于Voronoi图的kNN算法，主要是利用Voronoi图做预计算。解决方案包含两个过程：过滤过程和精炼过程。在过滤过程中会生成一个候选集合，在该集合中包含了所有的下一个可能的查询结果。而精炼过程的主要工作是利用障碍距离和邻接生成点对候选集合进行剪枝操作。2基本定义定义1(Voronoi图3) 给定一组数据点的集合Q一P1一，P。)c R2，其中21时，假设count(q，m)z，0z女，那么count(q，P女+1)是+1。

11、又由Voronoi图的定义可知，A+是mfP-，A的一个邻接生成点。因此，可以得到count(q，P川)max(count(q，pz)+1是+1，性质4得证，证毕。根据性质4得到算法1，算法1首先初始化3个队列Computedist、Accessed和Candidate,Set，分别用于存放将要计算的数据点及其到查询点的距离、已被访问的节点和候选集合。由VN(q)求出查询点q的邻接生成点集合，计算这些生成点到q点的障碍距离，将这些生成点放入Computedist队列中。然后从Computedist队列中取出一个元素i，若它到q点经过的数据点个数不大于k，则将它加入到候选集合CandidateS

12、et中。然后求出i的生成点集合，若这些生成点没有被访问过，则将其记住，放入Computedist和Accessed队列中。最后返回候选集合。算法1 filter(P，q，女)输入：查询点q，查询对象集P，kNN查询的k值输出：候选集合CandidateSetbegin1Computedist=0，Accessed=O，CandidateSet=0；初始化3个队列2while P。in VN(q)do3 add(P。，1)into Computedist；将P。及其到查询点q的距离加入Computedist中4 add P。into Accessed；标记P，被访问过5endwhile6whil

13、e notempty(Computedist)do7Pop an element i；从队列中取出元素i8 if count(q，i)k then判断q到点i经过的数据点个数是否大于kadd(i，d(q，i)into CandidateSet；1于等于k，将i及其到达查询点q的距离放人CandidateSet中while P。7 in VN(i)doif notVisited(p。7)then女D果px没被访问count(q，P。)=count(q，i)+1；count(q，i)JJIl 1end ifadd(count(q，m 7)，风7)into Computedist；将查询点q及其到达

14、P。7的最少数据点个数加入Computedist中add P，7 into Accessed；标记px被访问end whileendifelse continue； 175 o；mn心H埔万方数据19end while20return CanclidateSet；返回候选集合end32精炼过程在过滤过程完成之后，得到了一个候选集合，在精炼过程中要对该集合进行剪枝操作。利用性质2、性质3对候选集合内的对象进行精炼，对不符合条件的对象进行剪枝。性质5查询点q与对象P之间经过若干对象如P，连接P与P，若无障碍物，则count(q，户)增加1。如果count(q，声)矗，则对象P被剪枝。证明：查询点q

15、与对象P：之间若没有障碍物，则说明查询点q到对象p，的欧氏距离一定比到对象P的欧氏距离近，若q到P之间存在障碍物，那么查询点q到P，的障碍距离也一定比到P的近。当忌一1时，这样的以就有可能是q的1NN，而q一定不是P的1NN；当愚1时，只要以不小于k，那么查询点q的kNN一定不包括P，即count(p，q)忌时，P一定不是候选集里的对象，证毕。根据性质5得到算法2，算法2首先查看候选集中的每一个对象p与其查询点q，若p与它经过的对象之间有k个以上无障碍物的对象，则P被剪枝。对于候选集中的每个对象P，以查询点q为圆心，以I户qI为半径做圆，若在此候选集中的对象e也在这个圆内，判断P与e之间是否存

16、在障碍物，若对于一个P，有多于个障碍物，则P就从候选集合中移除。算法2 prune_by_obs(CandidateSet，q，O，是)输入：候选集合CandidateSet，查询点q，障碍物集O，kNN查询的k值输出：筛选后的候选集合CandidateSetbegin1while P in CandidateSet do2 makeCircle(q，d(q，p)；以点P为圆心、以d(q，p)为半径做圆round(q)3while e in round(q)nCandidateSet do lie同时在round(q)内和候选集合中t if notobstacle(p，e)thenp和e之间没

17、有障碍物5 count+；计数器加16 end if7 else continue；8 endwhile9 if countk then计数器大于等于k10 Remove P from CandidateSet；将对象P从候选集合中移除11 endif12 else continue；13end while14return CandidateSet；返回候选集合end性质6若候选集合中点P的邻接生成点都被剪枝了，则点P也被剪枝。证明：假设点P在候选集合中，且点P的邻接生成点都被剪枝。由Voronoi图的性质知，q到P一定经过P的邻接生成点，而count(q，p)七，从而得到count(q，p)

18、矗+1女，由性质5知P被剪枝，证毕。根据性质6得到算法3，算法3设置了一个变量来标记对象是否需要被剪枝。若候选集合中任意对象P的全部邻 】76 接生成点都被剪枝了，则对象P也被剪枝。算法3 prune_by_neigh(CandidateSet，q)输入：候选集合CandidateSet，查询点q输出：新的候选集合CandidateSetbegin1flag=0；2while P in CandidateSet do3 while eEVN(p)do4 if eE CandidateSet then5 flag=1；6 end if7 else continue：8 end while9 if

19、 flag=0 then10 remove P from CandidateSet；从候选集合CandidateSet中移除P11end if12else continue；13end while14return CandidateSet；end33障碍空间中基于Voronoi的kNN算法描述下面介绍在障碍空间中，给出查询点q、数据点集P、障碍物集0的kNN查询。算法4首先根据空间的数据点和障碍物画出Voronoi图。然后开始进行过滤过程，在过滤过程中只取那些到查询点q经过的数据点个数不大于k的数据点放人候选集合。接下来是精炼过程，在精炼过程中查看候选集中的点P与它到q之前的所有点之间的距离，

20、若有不少于k个点无障碍物，则这样的点P，就可以从候选集合中取出，若候选集合中存在点办，它的所有邻接生成点都被移出候选集，则此点p也被移出候选集。最后对候选集合中的每个对象P计算它的第k个近邻点仇，若查询点q到P的障碍距离d(户，q)d(P，Pk)thenpk是q的k个最近邻8 remove P from CandidateSet；从候选集合CandidateSet中移除P9 end if10 end while11_endwhile12return CandidateSet；end34障碍空间中新增点对kNN的影响若数据集P增加数据点，那么给定查询点的kNN将会万方数据受到一定的影响。为了方便

21、研究，给出了处理数据集一次增加一个数据点的方法。当增加多个数据点时，可根据需要对Voronoi图进行局部重构。若新增加的点在根据算法所画的圆内，重新调用算法4，若不在，则返回原有的查询结果。算法5是新增点对障碍空间中kNN查询的影响算法。算法5首先将新增加的点加入到数据集P 7中，然后建立3个空队列kNN-m、NewkNNn和Dist-o分别用于存储查询点的查询结果、查询点新的k最近邻点和查询点与k最近邻点的障碍距离。接下来调用kNNObs算法，将所得到的k最近邻点加入到kNNm队列中。然后计算q到kNNm-队列内的任意P，的最短障碍距离，将q到P，的最短障碍距离加入DistI-o队列中。以q

22、为圆心、d(q，A)为半径做圆。如果新增点W位于某一个或某几个圆内，重新调用kNNObs算法，将k最近邻点存储于NewkNN超中，然后返回NewkNNn。否则返回原来的kNNm。算法5 ADDkNN-Obs(q，k，P，0，叫)输入：查询点q，kNN查询的k值，数据集P，障碍物集合0，新增点W输出：点q的新的kNNbegin1P 7=add w into P；将新增加的点W加入到数据集P中得到新的数据集P 72kNNm=O，NewkNNn=D；Disto=O；初始化3个队列3call kNNObs(q，k，P，o)；调用kNN-Obs算法得到q的kNN为PlPzPk4add P1，P2，Pk

23、into kNNm；将Pl，P2，Pk NA到kNNm队列中5d(P。，q)一d(P。，b：)+d(b：，q)；计算kNNm队列中任意的P。与q之间的障碍距离，其中b：是P。与q之间的点6add d(p。，q)into Dis(o；将P。加入到Disto队列7makeCircle(q，d(q，P。)；以点q为圆心，d(q，P，)为半径做圆round(q)8if wE round(q)then9 call kNN-Obs(q，k，P，0)；重新调用kNNObs算法得到q的新的kNN为Pl，P2，pk10 add P1，P2，Pk into NewkNNn；将Pl，P2，pk加人到NewkNNn队

24、列中1 1 return NewkNN-n；返回NewkNNn12end if13else return kNNm；in果新增加点W不在圆内，返回kNNmend35障碍空间中删除点对kNN的影响若从数据集P中删除数据点，则对查询点的kNN有一定的影响，若删除点在结果的集合中，则重新调用kNNObs算法；若不在，则返回原来的结果。根据以上的分析可得到解决删除点后对障碍空间中kNN的影响问题的算法。算法6是删除点后对障碍空间中kNN查询的影响算法。算法6首先在数据集P中删除任意点得到数据集P，然后建立两个空队列kNNm昶l f、f鲍c，女NN行分别用于存储查询点的查询结果和查询点新的最最近邻点。接

25、下来调用kNNObs算法，将所得到的k最近邻点加人kNNI-m队列中。如果删除点位于kNNm中，重新调用kNNObs算法，将k最近邻点存储于NewkNNn，返回NewkNNn；否则，返回原来的矗NNm。算法6 DENkNN-Obs(q，k，P，O，d)输人：查询点q，数据集P，障碍物集合O，kNN查询的k值，删除点d(dP)输出：查询点q新的kNNbegin1P一remove d from P；数据集P中删除d得到数据集P2kNNm=O，NewkNNn=D；初始化两个队列3call kNNObs(q，k，P，O)；调用kNNObs算法得到点q的kNN为Pl，Pz，Pk4add P1，P2，Pi

26、nto kNN-m；将P1，P2，Pi加入到kNNm队列中5if dff kNNmthen6 call kNNObs(q，k，P，0)；重新调用kNNObs算法得到新的kNN7add Pl，P2，Pk into NewkNNn；将Pl，P2，Pk加入到NewkNNn队列中8 retum NewkNNn；返回NewkNNn9end if10else return kNNm；女tl果删除点不在结果集合中，返回kNNmend4实验与分析本节将所提出的kNNObs算法、ADDkNNObs算法、DENkNNObs算法与文献13中的算法(PostPruning算法)进行了比较分析，为便于比较，对实验算法细

27、节进行了局部调整。每次实验的结果为执行100次的平均效果。实验运行环境为：2OGHz CPU、4GB内存、Windows 7操作系统。测试数据集P、障碍集0和查询点口是由数据生成器产生的随机分布的空间数据，其中数据集是点数据构成的，障碍集是由线段构成的。首先是正值的影响。图2和图3分别给出了k值的变化对CPU时间和磁盘I0代价的影响。实验将P的数据量设为20000个，0的数据量设为10000个。图2 k值对CPU运行时间的影响图3女值对磁盘I0代价的影响由图2给出了k值的变化对CPU时间的影响。k值从1变化到20的过程中，CPU时间随着k值的增大而逐渐变大。kNNObs算法需要构造Vorono

28、i图，所以当k较小时，CPU时间比PostPruning算法长，但随着k值的增加，kNNObs算 1 77 百E一j山。瑚珊瑚嘲瑚。唾枷叵扭万方数据法的优势就逐渐显现出来。图3给出了志值的变化对磁盘I0代价的影响。两种算法的磁盘I0都是随着k的增加而增加。这是因为k值越大，需要访问的数据点越多，磁盘IO代价越大。但是由于kNN一0bs算法只访问候选集中的数据点，因此在一些情况下，其磁盘IO代价相对会小。其次是障碍物个数的影响，图4和图5分别给出了障碍物个数的变化对CPU时间和磁盘I0代价的影响。实验将P的数据量设为30000个，k值设为10。图4障碍物的个数对于CPU时间的影响f-l二Po_t

29、hl口岫警：一岍嘶一r謦枷l- 一囊毒墨l：；l-I_I_I J_表1 ADDkNN-Obs与PostPruning性能对比表2显示在数据集合中删除点后的DENkNN-Obs算法与对比算法计算kNN结果时的性能对比，执行时间同样是取 178100次测试的平均值。由数据分析可知，DENkNN-Obs算法在处理数据集中删除点后的k最近邻查询时优于Post-Pru-ning算法。表2 DENkNN-Obs与PostPruning性能对比结束语随着无线通信技术、全球定位系统、地理信息系统以及移动计算等现代化技术的迅速发展，基于位置的服务(Location-BasedService，LBS)得到广泛的应

30、用。而kNN是LBS中最常用的查询类型，具有广泛的应用前景。本文分析了现有kNN查询方法存在的不足，在此基础上对基于障碍空间的kNN查询方法进行了研究。现实生活中的大多数查询请求都不是在理想的欧氏空间中，并且现有算法随着数据点的增加其查询的时间会增加较大。为了有效处理障碍空间中的kNN问题，本文提出基于Voronoi图的kNNObs算法，解决方案包含两个过程：过滤过程和精炼过程。在过滤过程中得到一个候选结果的集合，而精炼过程的主要工作是对候选结果的集合进行进一步的剪枝。实验证明在一定情况下，kNNObs算法提高了障碍空间下的kNN查询效率。未来的研究重点主要集中在以下两点：1基于Voronoi

31、图的不确定拓扑关系和不确定反向最近邻查询方法。2路网中基于Voronoi图的NN方法及几种变体结构。参考文献13郝忠孝时空数据库查询与推理M北京：科学出版社，2010E2李松，张丽平，孙冬璞空间关系查询与分析M哈尔滨：哈尔滨工业大学出版社，20113Secl J R，Urrutia JVorouoi diagramshandbook OU computa-tioual geometryMOttawa：Elsevier Science，2000：2012904Jegou H，Inria R，Schmid CProduct Quantization for NearestNeighbor Sear

32、chJIEEE Transactions on Pattern Analysisand Machine Intelligence，2011，33(1)：1171285Geng Zhao，Xuan K F，Johanna R，et a1VICVoronoiBasedContinuous k Nearest Neighbor Search in Mobile NavigationJIEEE Transactions on Industrial Electronics，201 1，58(6)：224722576Esmaeili M M，Ward R K，Fatoureehi M A Fast App

33、roximateNearest Neighbor Search Algorithm in the Hamming SpaceJIEEE Transactions on Pattern Analysis and Machine Intelligence，2012：248124887Zheng Ligang，Qiu Guo-ping，Huang Jiwu，et a1Fast and accurate Nearest Neighbor search in the manifolds of symmetric po-sitive definite matricesCAcoustics，Speech a

34、nd Signal Processing2014：380438088Zhang Liping，Zhao Jiqiao，Li Song，et a1Research on Methodsof Construction of Voronoi Diagram and Nearest Neighbor Query in Constrained RegionsJComputer Science，2014，41(9)：220224，247(in Chinese)张丽平，赵纪桥，李松，等Voronoi图的构建与受限区域内的最近邻查询方法研究J计算机科学，2014，41(9)：220224，247(下转第187

35、页)万方数据taSIGMOD，2009：1 93206E23 Antunes C，Oliveira A L Generalization of pattern growth me-thods for sequential pattern mining with gap constraintsMMachine Learning and Data Mining in Pattern Recognition2003：2392513Pei J，Han J，Mortazavi B，et a1Prefixspan：mining sequentialpatterns efficiently by prefi

36、x-projected pattern growthCProceedings of the 17th International Conference on Data Engineering(ICDE)2001：2152264Wu E，Diao Y，Rizvi&High performance complex event pro-cessing over streamsC3 ff Proceedings of the 32th SIGMOD International Conference on Management of Data SIGMOD，2006：407-4185Alex D，Rob

37、ert RSubrahmanian V&Probabilistic temporal databasesJACM Transaction on Database Systems，2001，26(I)：41956Barga R S，Goldstein J，All M，et a1Consistent streaming th-rough timeta vision for event streamprocessingCThe 3rdBiennial Conference on Innovative Data Systems ResearchIDAR20077Wu s，Chen Y，Mining n

38、onambiguous temporal patterns for intervalbased eventsJ 1IEEE Transactions on Knowledge andData Engineering，2007，19(6)：7427588Patel D，Hsu W，Lee M I。Mining relationships among intervalbased events for classificationC1Proceedings of the 34th SIGMOD International Conference on Management of DataSIGMOD，

39、2008：39340493 Hamnlad M A，et a1Seheduling for shared window joins overdata streamsCThe 29th International Conference on VeryLarge Data Bases2003，29：29730810,l Liu M，Li M，Golovnya D，et a1Sequence pattern query processing over outof-order event streamscProceedings of the25th International Conference o

40、n Data Engineering(ICDE)2009：27429511Eyerman S，Eeckhout L，Karkhanis T，et a1A mechanistic per-formance model for superscalar OUtof_order processorsJACM Transactions on Computer Systems(T。CS)，2009，27(2)：82483312Wang F，Liu S，Liu PComplex RFID event processingJTheInternational Journal on Very Large Data

41、 Bases(VLDBJ)，2009，18(4)：913931131 Papapetrou P，Kollios G，Selaroff S，et a1Mining frequent arrangements of temporal intervalsJKnowledge&InformationSystems，2009，21(2)：133171143 Ding L，Mehta N，Rundensteiner E A，et a1Joining punctuatedstreamsMAdvances in Database Technology(EDBT)2004：58760415Kam P S，Fu

42、A WDiscovering temporal patterns for intervalbased eventsCProceedings of the 2nd International Conic-rence on Data Warehousing and Knowledge Discovery2000：317-326163 Barga R S，Goldstein J，Ali M，et a1Consistent streaming through time：a vision for event stream processingC?The 3rdBiennial Conference on

43、 Innovative Data Systems Research2006：363-374173 Zhou C J，Meng X FA framework of complex event detectionand operation in pervasive computingC,lThe Third SIGMODPhD Workshop on Innovative Database ResearcL 2009(上接第178页)9Yuan P S，Sha C F，Wang X L，et a1c-Approximate nearestneighbor query algorithm based

44、 on learning for highdimensionaldataJJournal of Software，2012，23(8)：20182031(in Chinese)袁培森，沙朝锋，王晓玲，等一种基于学习的高维数据c-近似最近邻查询算法J软件学报，2012，23(8)：20182031101 Lu Yansheng，He Ya-jun。Pan PengImprovement of the EINNAlgorithm for NN Query TraversingJComputer Engineeringand Science，2005，27(7)：6264(in Chinese)卢炎

45、生，何亚军，潘鹏EINN最近邻居查询索引遍历算法改进口计算机工程与科学，2005，27(7)：62641l,l Li Song，Zhang LipingSimple Continues Near Neighbor ChainQuery in Dynamic Constrained RegionsJComputer Science，2014，41(6)：136一141(in Chinese)李松，张丽平动态受限区域内的单纯型连续近邻链查询方法J1计算机科学，2014，41(6)：13614112Gao Y，Zheng R Continuous obstructed nearest neighbo

46、r queriesin spatial databasesCProceedings of the 28th ACM SIGMoD International Conference of Management of Data(Sigmod09)New York，USA，2009：577-590131 Nutanong S，Tanin E，Zhang RuiIncremental evaluation of visible nearest neighbor queriesJ,1IEEE Transactions on Knowledge Engineering，2010，22(5)：6656811

47、4Gao Y，Yang J C，Chen G，et a1On efficient obstructed reversenearest neighbor query processingCProcof the 19th IntConfon Advances in Geographic Information SystemsChicago：ACM Press，201 1：19112015Li Chuan-wen，Gu Yu，Qi Jianzhonget a1A safe region basedapproach to moving KNN queries in obstructed spaceJKnowledge and Information Systems，2014，24(3)：17919516Wang Yanqiu，Zhang Rui，Xu Chuanfei，et a1Continuous visible k nearest neighbor query on moving objectsJInformationSystems，2014，44(8)：1-21173