Computer Science ›› 2015, Vol. 42 ›› Issue (8): 231-235.

Previous Articles     Next Articles

Reverse Nearest Neighbor Query Based on Voronoi Diagram for Road Network

ZHANG Li-ping, JING Hai-dong, LI Song and CUI Huan-yu   

  • Online:2018-11-14 Published:2018-11-14

Abstract: In view of the shortage of exisiting reverse nearest neighbour(RNN)query method in road network,NVD-RNN algorithm making use of network Voronoi diagram(NVD) has good effect.The algorithm divides the road network into small Voronoi regions and adopts two processes:filtering and refining processes.The filtering process mainly stores possible query results in advance.The major task of refining process is to find query results from potential outcome sets,in addition it provides ADDNVD-RNN algorithm to dispose of newly increased points and DENVD-RNN algorithm to cope with deleted points any further.The experiment demonstrates that the algorithm has obvious advantages in dealing with reverse nearest neighbor in road network.

Key words: Network Voronoi diagram,Reverse nearest neighbor query,Road network environment

[1] Shekhar S,Chawla S.空间网络数据库[M].北京:机械工业出版社,2004 Shekhar S,Chawla S.Space Network Database[M].Beijing:Machinery Industry Press,2004
[2] 马希荣,王嵘.一种基于最近邻决策的点集分类方法的确定与实现[J].计算机科学,2007,4(12):182-183 Ma Xi-rong,Wang Rong.A New Method to Class a Point Set Based on Nearest-Neighbour Decision Boundaries[J].Computer Science,2007,4(12):182-183
[3] 郭薇,郭菁,胡志勇.空间数据库索引技术[M].上海:上海交通大学出版社,2006:1-7 Guo Wei,Guo Jing,Hu Zhi-yong.The technology of spatial database indexing[M].Shanghai:Shanghai Jiaotong University Press,2006:1-7
[4] 张丽平,李松,郝忠孝.球面上的最近邻查询方法研究[J].计算机工程与应用,2011,47(5):126-129 Zhang Li-ping,LI Song,Hao Zhong-xiao.Research of methods for nearest neighbor query on spherical surface[J].Computer Engineering and Applications,2011,7(5):126-129
[5] 朱庆生,唐汇,冯骥.一种基于自然最近邻的离群检测算法[J].计算机科学,2014,1(3):276-278,5 Zhu Qing-sheng,Tang Hui,Feng Ji.Outlier Detection Algorithm Based on Natural Nearest Neighbor[J].Computer Science,2014,41(3):276-278,5
[6] 李松,张丽平,朱德龙,等.动态受限区域内的单纯型连续近邻链查询方法[J].计算机科学,2014,1(6):136-141 Li Song,Zhang Li-ping,Zhu De-long,et al.Simple Continues Near Neighbor Chain Query in Dynamic Constrained Regions [J].Computer Science,2014,1(6):136-141
[7] Korn F,Muthukrishnan S.Influence sets based on reverse nearest neighbor queries [C]∥Proceedings of 2000 ACM SIGMOD International Conference on Management of Data.Dallas,Texas,USA,2000:201-212
[8] Yang C,Lin K.An index structure for efficient reverse nearest neighbor queries [C]∥Proceedings of 17th International Conference on Data Engineering.Heidelberg,Germany,2001:485-492
[9] Xia C,Hsu W,Lee M L.ERkNN:Efficient Reverse k-Nearest Neighbors Retrieval with Local kNN-Distance Estimation[C]∥Proceedings of CIKM 2005.Bremen,Germany.2005:533-540
[10] 郝忠孝,刘永山.空间对象的反向最近邻查询[J].计算机科学,2005,2(11):115-118 Hao Zhong-xiao,Liu Yong-shan.Reverse Nearest Neighbor Search in Spatial Database[J].Computer Science,2005,2(11):115-118
[11] Wu W,Yang F,Chan C,et al.FINCH:Evaluating Reverse k-Nearest-Neighbor Queries on Location Data[J].VLDB Endowment,2008,1(1):1056-1067
[12] 李松,郝忠孝.基于Voronoi图的反向最近邻查询方法研究[J].哈尔滨工程大学学报,2008,9(3):261-265 Li Song,Hao Zhong-xiao.Reverse nearest neighbor queries using Voronoi diagrams[J].Journal of Harbin Engineering University,2008,29(3):261-265
[13] Emrich T,Kriegel H,Mamoulis N,et al.Reverse-NearestNeighbor Queries on Uncertain Moving Object Trajectories[M]∥Database Systems for Advanced Applications.Springer,2014:92-107
[14] Sun H L,Jiang C,Liu J L,et al.Continuous Reverse Nearest Neighbor Queries on Moving Objects in Road Networks[C]∥The Ninth International Conference on Web-Age Information Management(WAIM 08).2008:238-245
[15] 齐峰,金顺福,刘国华,等.道路网络环境下的近似反k最近邻查询算法[J].小型微型计算机系统,2010,8(8):1599-1603 Qi Feng,Jin Shun-fu,Liu Guo-hua,et al.Approximation Reverse k-nearest Neighbor Queries in Road Network[J].Journal of Chinese Computer Systems,2010,8(8):1599-1603
[16] 朱彩云,刘国华,宋金玲,等.空间网络数据库中反k最近邻查询算法[J].小型微型计算机系统,2009,9(9):1781-1786 Zhu Cai-yun,Liu Guo-hua,Song Jin-ling,et al.Algorithm for Reverse k-Nearest Neighbor Queries in Spatial Network Databases[J].Journal of Chinese Computer Systems,2009,9(9):1781-1786
[17] Cheema M A,Zhang W,Lin X,et al.Continuous reverse k nearest neighbors queries in Euclidean space and in spatial networks[J].The VLDB Journal—The International Journal on Very Large Data Bases,2012,21(1):69-95
[18] Okabe A,Boots B,Sugihara K,et al.Spatial Tessellations,Concepts and Applications of Voronoi Diagrams(2nd ed)[M].John Wiley and Sons Ltd,2000
[19] Kolahdouzan M R,Shahabi C.Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases[C]∥Proceedings of the 30th International Conference on very Large Data Bases(VLDB).2004:840-851
[20] Data set [EB/OL].http://www.cs.fsu.edu/lifeifei/SpatialData-set.htm,2013
[21] Yin M L,Papadias D,Mamoulis N.Reverse nearest neighbors in large graphs[C]∥The 21st International Conference on Data Engineering.Tokyo,Japan,2005:301-304

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!