计算机科学 ›› 2019, Vol. 46 ›› Issue (1): 232-237.doi: 10.11896/j.issn.1002-137X.2019.01.036

• 软件与数据库技术 • 上一篇    下一篇

时间依赖路网中反向 k近邻查询

李佳佳, 沈盼盼, 夏秀峰, 刘向宇   

  1. (沈阳航空航天大学计算机学院 沈阳110136)
  • 收稿日期:2017-11-22 出版日期:2019-01-15 发布日期:2019-02-25
  • 作者简介:李佳佳(1987-),女,博士,讲师,CCF会员,主要研究方向为时空数据管理、不确定数据管理;沈盼盼(1990-),男,硕士生,主要研究方向为时态数据库管理;夏秀峰(1964-),男,博士,教授,CCF高级会员,主要研究方向为数据库理论与技术,E-mail:xiaxiufeng@163.com(通信作者);刘向宇(1981-),男,博士,讲师,主要研究方向为社交网络、隐私保护。
  • 基金资助:
    国家自然科学基金(61502317),辽宁省自然科学基金(201602559,201602568)资助

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

摘要: 在现存的反向k近邻查询方案中,比较高效的研究大多集中在欧氏空间或者静态路网,对时间依赖路网中的反向k近邻查询的研究相对较少。已有算法在兴趣点密度稀疏或者k值较大时,查询效率较低。对此,提出了基于子网划分的反向k近邻查询算法mTD-SubG。首先,将整个路网划分为大小相同的子网,通过子网的边界节点向其他子网进行扩展,加快对路网中兴趣点的查找速度;其次,利用剪枝技术缩小路网的扩展范围;最后,利用已有时间依赖路网下的近邻查询算法,判定查找到的兴趣点是否为反向k近邻结果。实验中将mTD-SubG算法与已有算法mTD-Eager进行对比,结果表明mTD-SubG算法的响应时间比mTD-Eager算法减少了85.05%,遍历节点个数比mTD-Eager算法减少了51.40%。

关键词: mTD-SubG算法, 反向k近邻(RkNN), 路网, 时间依赖

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

中图分类号: 

  • 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] 宋元隆, 吕光宏, 王桂芝, 贾吾财.
基于图卷积神经网络的SDN网络流量预测
SDN Traffic Prediction Based on Graph Convolutional Network
计算机科学, 2021, 48(6A): 392-397. https://doi.org/10.11896/jsjkx.200800090
[2] 朱润泽, 秦小麟, 刘嘉琛.
基于查询对象的路网Skyline查询中Why-not问题的研究
Study on Why-not Problem in Skyline Query of Road Network Based on Query Object
计算机科学, 2021, 48(6): 57-62. https://doi.org/10.11896/jsjkx.200700016
[3] 刘泽邦, 陈荦, 杨岸然, 李思捷.
面向矢量线数据的直线形状空间检索方法
Space Retrieval Method to Retrieve Straight Line for Vector Line Data
计算机科学, 2021, 48(11A): 117-123. https://doi.org/10.11896/jsjkx.210100084
[4] 熊亭, 戚湧, 张伟斌.
基于DCGRU-RF模型的路网短时交通流预测
Short-term Traffic Flow Prediction Based on DCGRU-RF Model for Road Network
计算机科学, 2020, 47(5): 84-89. https://doi.org/10.11896/jsjkx.190100213
[5] 韩京宇, 许梦婕, 朱曼.
路网上基于时空锚点的移动对象群体和个体运动监测方法
Detecting Group-and-individual Movements of Moving Objects Based on Spatial-Temporal Anchors of Road-network
计算机科学, 2020, 47(11): 294-303. https://doi.org/10.11896/jsjkx.191100083
[6] 阮子瑞,阮中远,沈国江.
基于交通路网的TASEP模型的扩展研究
Study of TASEP Model Based on Road Networks
计算机科学, 2020, 47(1): 265-269. https://doi.org/10.11896/jsjkx.181202418
[7] 张彤,秦小麟.
时间依赖路网上的移动对象K近邻查询算法
K Nearest Neighbors Queries of Moving Objects in Time-dependent Road Networks
计算机科学, 2020, 47(1): 79-86. https://doi.org/10.11896/jsjkx.181102231
[8] 孙中锋, 王静.
用于基于方面情感分析的RCNN-BGRU-HN网络模型
RCNN-BGRU-HN Network Model for Aspect-based Sentiment Analysis
计算机科学, 2019, 46(9): 223-228. https://doi.org/10.11896/j.issn.1002-137X.2019.09.033
[9] 周剑刚, 秦小麟, 张珂珩, 许建秋.
基于道路网的多移动用户动态Skyline查询
Dynamic Skyline Query for Multiple Mobile Users Based on Road Network
计算机科学, 2019, 46(9): 73-78. https://doi.org/10.11896/j.issn.1002-137X.2019.09.009
[10] 毛莺池,陈杨.
不确定性车辆路口的轨迹预测
Uncertain Vehicle Intersection Trajectory Prediction
计算机科学, 2018, 45(3): 235-240. https://doi.org/10.11896/j.issn.1002-137X.2018.03.037
[11] 董天阳, 尚跃辉, 程强.
方向感知的路网移动对象范围查询算法
Direction-aware Moving Object Range Query Algorithm in Road Network
计算机科学, 2018, 45(11): 210-219. https://doi.org/10.11896/j.issn.1002-137X.2018.11.033
[12] 余未,郑吉平,王海翔,王永阁,陈嘉良,江顺青.
空间Skyline查询处理:应用、研究与挑战
Spatial Skyline Queries:Applications,Research and Challenges
计算机科学, 2017, 44(2): 1-16. https://doi.org/10.11896/j.issn.1002-137X.2017.02.001
[13] 戴佳筑,华亮.
路网环境下敏感位置匿名区域的生成方法
Method of Anonymous Area Generation for Sensitive Location Protection under Road Networks
计算机科学, 2016, 43(3): 137-144. https://doi.org/10.11896/j.issn.1002-137X.2016.03.027
[14] 张丽平,经海东,李松,崔环宇.
路网中基于Voronoi图的反向最近邻查询方法
Reverse Nearest Neighbor Query Based on Voronoi Diagram for Road Network
计算机科学, 2015, 42(8): 231-235.
[15] 薛 明 许德刚.
基于云网格集成调度的防拥堵车辆路径规划算法
Anti Congestion Vehicle Path Planning Algorithm Based on Cloud Grid Integrated Scheduling
计算机科学, 2015, 42(7): 295-299. https://doi.org/10.11896/j.issn.1002-137X.2015.07.063
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!