面向时间依赖路网的空间索引方法

doi:10.19678/j.issn.1000-3428.0050009

计算机工程 ›› 2019, Vol. 45 ›› Issue (5): 127-134. doi: 10.19678/j.issn.1000-3428.0050009

面向时间依赖路网的空间索引方法

李佳佳,臧寅旭,刘向宇,夏秀峰,朱睿

沈阳航空航天大学计算机学院,沈阳 110136

收稿日期:2018-01-08 出版日期:2019-05-15 发布日期:2019-05-15
作者简介:李佳佳(1987—),女,讲师、博士,主研方向为智能交通、时态数据管理;臧寅旭,硕士研究生;刘向宇,讲师、博士;夏秀峰,教授、博士;朱睿,讲师、博士。
基金资助:
国家自然科学基金(61502317)。

Spatial Index Method for Time Dependent Road Network

LI Jiajia,ZANG Yinxu,LIU Xiangyu,XIA Xiufeng,ZHU Rui

School of Computer,Shenyang Aerospace University,Shenyang 110136,China

Received:2018-01-08 Online:2019-05-15 Published:2019-05-15

摘要/Abstract

摘要：

在兴趣点(POI)呈稀疏分布时,现有时间依赖路网中的k近邻查询方法效率较低,且无法高效支持多类型的POI查询。为此,建立基于POI分布的空间索引结构TDG。根据路径权值上、下界对预计算路径进行剪枝优化,在此基础上,提出一种索引更新策略与基于TDG的k近邻查询算法。实验结果表明,与启发式查询算法相比,该算法的扩展节点数量平均减少87.5%,查询响应时间平均缩短33%~66%。

关键词: 时间依赖路网, 多类型POI, 网格划分, 上、下界剪枝, k近邻查询

Abstract:

When Points of Interest(POI) are sparsely distributed,the existing k-nearest neighbor query method in time dependent road network is inefficient and can not support multi-type POI queries efficiently.Therefore,a spatial index structure TDG based on POI distribution is established.According to the upper and lower bounds of the path weights,pruning and optimization of the predicted paths is carried out.On this basis,an index update strategy and a TDG-based k-nearest neighbor query algorithm are proposed.Experimental results show that compared with heuristic query algorithm,the average number of extended nodes of the proposed algorithm is reduced by 87.5%,and the average response time to a query is reduced by 33%~66%.

Key words: time dependent road network, multi-type Points of Interest(POI), mesh generation, upper and lower bounds pruning, k-nearest neighbor query

中图分类号:

TP391

李佳佳,臧寅旭,刘向宇,夏秀峰,朱睿. 面向时间依赖路网的空间索引方法[J]. 计算机工程, 2019, 45(5): 127-134.

LI Jiajia,ZANG Yinxu,LIU Xiangyu,XIA Xiufeng,ZHU Rui. Spatial Index Method for Time Dependent Road Network[J]. Computer Engineering, 2019, 45(5): 127-134.

http://www.ecice06.com/CN/Y2019/V45/I5/127

参考文献

［1］ABEYWICKRAMA T,CHEEMA M A.Efficient landmark-based candidate generation for kNN queries on road networks［C］//Proceedings of the 22nd International Conference on Database Systems for Advanced Applications.New York,USA:ACM Press,2017:425-440.
［2］SUN Weiwei,CHEN Chunan,ZHENG Baihua,et al.An air index for spatial query processing in road networks［J］.IEEE Transactions on Knowledge and Data Engineering,2015,27(2):382-395.
［3］DEMIRYUREK U,BANAEI-KASHANI F,SHAHABI C. Efficient k-nearest neighbo research in time-dependent spatial networks［C］//Proceedings of the 21st International Conference on Database and Expert Systems Applications.Berlin,Germany:Springer,2010:432-449.
［4］WIN T N,HTOO H,OHSAWA Y.Bichromatic reverse kNN query algorithm on road network distance［M］//LU Hongjun,ZHOU Aoying.Web-age information management.Berlin,Germany:Springer,2015:469-472.
［5］BORUTTA F,NASCIMENTO M A,NIEDERMAYER J,et al.Reverse k-nearest neighbour schedules in time-dependent road networks［C］//Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems.Berlin,Germany:Springer,2015:27-36.
［6］WANG Siho,XIAO Xiaokui,YANG Yin,et al.Effective indexing for approximate constrained shortest path queries on large road networks［J］.Proceedings of VLDB Endowment,2016,10(2):61-72.
［7］HU Haibo,LEE D L,LEE V C S.Distance indexing on road networks［C］//Proceedings of the 32nd International Conference on Very Large Data Bases.New York,USA:ACM Press,2006:894-905.
［8］HU Haibo,XU Jianliang.Fast nearest neighbor search on road networks［C］//Proceedings of International Conference on Advances in Database Technology.Berlin,Germany:Springer,2006:186-203.
［9］ZHONG Ruicheng,LI Guoliang,TAN K L,et al.G-tree:an efficient index for KNN search on road networks［C］//Proceedings of the 22nd ACM International Conference on Information and Knowledge Management.New York,USA:ACM Press,2013:2175-2189.
［10］LEE K C K,LEE W C,ZHENG Baihua,et al.ROAD:a new spatial object search framework for road networks［J］.IEEE Transactions on Knowledge and Data Engineering,2010,24(3):547-560.
［11］LI Lei,JIWON K,JIAJIE X,et al.Time-dependent route scheduling on road networks［J］.SIGSPATIAL Special,2018,10(1):10-14.
［12］CRUZ L A.k-nearest neighbors queries in time-dependent road networks［J］.Journal of Information and Data Management,2013,3(3):56-60.
［13］KOMAI Y,NGUYEN D H,HARA T,et al.kNN search utilizing index of the minimum road travel time in time-dependent road networks［C］//Proceedings of 2014 IEEE International Symposium on Reliable Distributed Systems Workshops.Washington D.C.,USA:IEEE Press,2014:256-264.
［14］KOLAHDOUZAN M,SHAHABI C.Voronoi-based knn search in spatial networks［EB/OL］.［2018-01-02］.https://infolab.usc.edu/DocsDemos/VoronoiKNN_vldb2004.pdf.
［15］谭国真,高文.时间依赖的网络中最小时间路径算法［J］.计算机学报,2002,25(2):165-172.

[1]	党小超, 李月霞, 郝占军, 张彤. 一种基于改进蚁群算法的三维K-栅栏覆盖算法[J]. 计算机工程, 2020, 46(2): 221-229.
[2]	谭励,陈玉程. 复杂区域的有向传感器网络覆盖优化算法[J]. 计算机工程, 2015, 41(4): 14-18,25.
[3]	吴玲达, 曹叡, 杨超, 蒋杰. 基于数字地球的林火灾害建模[J]. 计算机工程, 2012, 38(17): 261-264.
[4]	王继良, 陈朋, 周四望. 基于不规则网格的传感数据Kriging插值算法[J]. 计算机工程, 2012, 38(08): 76-78.
[5]	陈曦, 马一峰. 空间数据聚类中的网格粒度求解方法[J]. 计算机工程, 2011, 37(19): 65-67.
[6]	亢宁, 韩国栋, 张震. 基于NoC系统级平面规划图的网格划分[J]. 计算机工程, 2010, 36(23): 291-293.

选择文件类型/文献管理软件名称

选择包含的内容

面向时间依赖路网的空间索引方法

Spatial Index Method for Time Dependent Road Network

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

面向时间依赖路网的空间索引方法

Spatial Index Method for Time Dependent Road Network

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价