计算机科学 ›› 2019, Vol. 46 ›› Issue (1): 232-237.doi: 10.11896/j.issn.1002-137X.2019.01.036
李佳佳, 沈盼盼, 夏秀峰, 刘向宇
LI Jia-jia, SHEN Pan-pan, XIA Xiu-feng, LIU Xiang-yu
摘要: 在现存的反向k近邻查询方案中,比较高效的研究大多集中在欧氏空间或者静态路网,对时间依赖路网中的反向k近邻查询的研究相对较少。已有算法在兴趣点密度稀疏或者k值较大时,查询效率较低。对此,提出了基于子网划分的反向k近邻查询算法mTD-SubG。首先,将整个路网划分为大小相同的子网,通过子网的边界节点向其他子网进行扩展,加快对路网中兴趣点的查找速度;其次,利用剪枝技术缩小路网的扩展范围;最后,利用已有时间依赖路网下的近邻查询算法,判定查找到的兴趣点是否为反向k近邻结果。实验中将mTD-SubG算法与已有算法mTD-Eager进行对比,结果表明mTD-SubG算法的响应时间比mTD-Eager算法减少了85.05%,遍历节点个数比mTD-Eager算法减少了51.40%。
中图分类号:
[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,MACDO 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 |
|