Computer Science ›› 2019, Vol. 46 ›› Issue (1): 232-237.doi: 10.11896/j.issn.1002-137X.2019.01.036

• Software & Database Technology • Previous Articles     Next Articles

Reverse k Nearest Neighbor Queries in Time-dependent Road Networks

LI Jia-jia, SHEN Pan-pan, XIA Xiu-feng, LIU Xiang-yu   

  1. (School of Computer Science,Shenyang Aerospace University,Shenyang 110136,China)
  • Received:2017-11-22 Online:2019-01-15 Published:2019-02-25

Abstract: Most existing efficient algorithms for reverse k nearest neighbor query focus on the Euclidean space or static networks,and few of them study the reverse k nearest neighbor query in time-dependent networks.However,the exis-ting algorithm is inefficient if the density of interest points is sparse or the value of k is large.To address these problems,this paper proposed a sub net division based reverse k nearest neighbor query algorithm mTD-SubG.Firstly,the entire road network is divided into subnets with the same size,and they are expanded to other subnets through the border nodes to speed up the search process for interest points.Secondly,the pruning technology is utilized to narrow the expansion range of road network.Finally,the existing nearest neighbor query algorithm of time-dependent road networks is used for each searchedinterest points to determine whether it belongs to the reverse k nearest neighbor results.Extensive experiments were conducted to compare the proposed algorithm mTD-SubG with the existing algorithm mTD-Eager.The results show that the response time of mTD-SubG is 85.05% less than that of mTD-Eager,and mTD-SubG reduces the number of traversed nodes by 51.40% compared with mTD-Eager.

Key words: mTD-SubG algorithm, Reverse k nearest neighbor, Road networks, Time-dependent

CLC Number: 

  • TP311
[1]LI Y H,LI G H,DU X K.Study on continuous bichromatic reverse k nearse neighbor query processing in road networks[J].Computer Science,2012,39(11):131-136.(in Chinese)<br /> 李艳红,李国徽,杜小坤.路网中双色数据集上连续反向k近邻查询处理的研究[J].计算机科学,2012,39(11):131-136.<br /> [2]DEMIRYUREK U,BANAEIKASHANI F,SHAHABI C.Towards K-Nearest Neighbor Search in Time-Dependent Spatial Network Databases[C]//International Conference on Databases in Networked Information Systems.Springer-Verlag,2010:296-310.<br /> [3]DEMIRYUREK U,BANAEI-KASHANI F,SHAHABI C.Efficient K-Nearest Neighbor Search in Time-Dependent Spatial Networks[M]//Database and Expert Systems Applications.Springer Berlin Heidelberg,2010:432-449.<br /> [4]CRUZ L A,NASCIMENTO M A,MACDO J A F D,et al.K-nearest neighbors queries in time-dependent road networks[J].Journal of Information & Data Management,2012,3(3):211-226.<br /> [5]BORUTTA F,NASCIMENTO M A,NIEDERMAYER J.Mono-chromatic RkNN queries in time-dependent road networks[C]//ACM Sigspatial International Workshop on Mobile GeographicInformation Systems.ACM,2014:26-33.<br /> [6]LI L,HUA W,DU X,et al.Minimal on-road time route scheduling on time-dependent graphs[J].Proceedings of the Vldb Endowment,2017,10(11):1274-1285.<br /> [7]YANG Y,GAO H,YU J X,et al.Finding the cost-optimal path with time constraint over time-dependent graphs[J].Procee-dings of the Vldb Endowment,2014,7(9):673-684.<br /> [8]WANG S,LIN W,YANG Y,et al.Efficient Route Planning on Public Transportation Networks:A Labelling Approach[C]//Acm Sigmod International Conference on Management of Data.ACM,2015:967-982.<br /> [9]ZHENG B,SU H,HUA W,et al.Efficient Clue-Based Route Search on Road Networks[J].IEEE Transactions on Knowledge &Data Engineering,2017,29(9):1846-1859.<br /> [10]DEMIRYUREK U,SHAHABI C.Hierarchical and exact fastest path computation in time-dependent spatial networks:US,US8660789[P].2014-02-25.<br /> [11]FOSCHINI L,HERSHBERGER J,SURI S.On the Complexity of Time-Dependent Shortest Paths.[C]//Acm-siam Symposium on Discrete Algorithms.Springer US,2011:327-341.<br /> [12]DELLING D.Time-Dependent SHARC-Routing[J].Algorithmica,2011,60(1):60-94.<br /> [13]LI L,ZHOU X,ZHENG K.Finding Least On-Road Travel Time on Road Network[C]//Australasian Database Confe-rence.Springer International Publishing,2016:137-149.<br /> [14]LIN W,LIN W,LIN W,et al.Effective indexing for approximate constrained shortest path queries on large road networks[J].Proceedings of the Vldb Endowment,2016,10(2):61-72.<br /> [15]MAN L Y,PAPADIAS D,MAMOULIS N,et al.Reverse nearest neighbors in large graphs[J].IEEE Transactions on Know-ledge & Data Engineering,2006,18(4):540-553.<br /> [16]SAMET H,SANKARANARAYANAN J,ALBORZI H.Scalable network distance browsing in spatial databases[C]//ACM SIGMOD International Conference on Management of Data.ACM,2008:43-54.<br /> [17]LU B L,CUI X Y,LIU N.Continuous k-nearest neighbor query processing in network[J].Computer Engineering and Design,2014(7):2395-2401.(in Chinese)<br /> 卢秉亮,崔晓玉,刘娜.路网中连续反向k近邻查询处理[J].计算机工程与设计,2014(7):2395-2401.<br /> [18]LU B L,CUI X Y,LIU N.Bichromatic k-nearest neighbor query processing in network[J].Journal of Chinese Computer Systems,2015,36(2):266-270.(in Chinese)<br /> 卢秉亮,崔晓玉,刘娜.路网中双色反向k近邻查询处理[J].小型微型计算机系统,2015,36(2):266-270.<br /> [19]MAN L Y,MAMOULIS N.Reverse Nearest Neighbors Search in Ad-hoc Subspaces[C]//International Conference on Data Engineering.IEEE,2006:76-76.<br /> [20]PAPADIAS D,ZHANG J,MAMOULIS N,et al.Query Processing in Spatial Network Databases[C]//Morgan-Kaufmann.2003:802-813.
[1] ZHANG Tong,QIN Xiao-lin. K Nearest Neighbors Queries of Moving Objects in Time-dependent Road Networks [J]. Computer Science, 2020, 47(1): 79-86.
[2] YU Wei, ZHENG Ji-ping, WANG Hai-xiang, WANG Yong-ge, CHEN Jia-liang and JIANG Shun-qing. Spatial Skyline Queries:Applications,Research and Challenges [J]. Computer Science, 2017, 44(2): 1-16.
[3] DAI Jia-zhu and HUA Liang. Method of Anonymous Area Generation for Sensitive Location Protection under Road Networks [J]. Computer Science, 2016, 43(3): 137-144.
[4] YANG Xu-hua and ZHOU Shi-jie. Double Layers Routing Algorithm on Large Road Networks Based on Overlapping Communities Detecting [J]. Computer Science, 2015, 42(Z6): 285-289.
[5] SHI Chang-yue,QIN Xiao-lin,XU Jian-qiu and HU Cai-ping. Location Range-based Skyline Query in Road Networks [J]. Computer Science, 2014, 41(9): 190-195.
[6] SUN Jing-hao,WU Xiong,TAN Guo-zhen,YAN Chao. Time-dependent Chinese Postman Problem Solved by Two Layers SA/GA Algorithm [J]. Computer Science, 2011, 38(5): 93-95.
[7] TAN Guo-zhen,SUN Jing-hao,XIAO Hong-ye,LU Kai. Branch-bound Algorithm for Undirected Time-depended Chinese Postman Problem [J]. Computer Science, 2011, 38(2): 110-113.
[8] LIAO Wei,WU Xiao-ping,HU Wei,ZHONG Zhi-nong. Processing of k Nearest Neighbor Queries Based on Shortest Path in Road Networks [J]. Computer Science, 2010, 37(11): 180-183.
[9] LIAO Wei , WU Xiao-ping, YAN Cheng-hua, ZHONG Zhi-nong. Novel Method for Continuous Queries Processing in Road Networks [J]. Computer Science, 2009, 36(9): 151-153.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!