Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (1): 120-125.DOI: 10.11772/j.issn.1001-9081.2017071670

Previous Articles     Next Articles

Improved time dependent fast travel time algorithm by dynamically selecting heuristic values

LI Jiajia, LIU Xiaojing, LIU Xiangyu, XIA Xiufeng, ZHU Rui   

  1. College of Computer Science, Shenyang Aerospace University, Shenyang Liaoning 110136, China
  • Received:2017-07-05 Revised:2017-08-23 Online:2018-01-10 Published:2018-01-22
  • Supported by:
    This work is partially supported by National Natural Science Foundation of China (61502317).

基于动态选择启发值的改进TD-FTT算法

李佳佳, 刘晓静, 刘向宇, 夏秀峰, 朱睿   

  1. 沈阳航空航天大学 计算机学院, 沈阳 110136
  • 通讯作者: 李佳佳
  • 作者简介:李佳佳(1987-),女,辽宁绥中人,讲师,博士,CCF会员,主要研究方向:时态数据管理、智能交通;刘晓静(1991-),女,山西大同人,硕士研究生,主要研究方向:时态数据库管理;刘向宇(1981-),男,辽宁铁岭人,讲师,博士,主要研究方向:社交网络、隐私保护;夏秀峰(1964-),男,山东胶南人,教授,博士,CCF高级会员,主要研究方向:数据仓库、NoSQL数据库;朱睿(1982-),男,山东莱芜人,讲师,博士,主要研究方向:流数据管理、时空众包。
  • 基金资助:
    国家自然科学基金资助项目(61502317)。

Abstract: The existed TD-FTT (Time Dependent Fast Travel Time) algorithm, for answering K Nearest Neighbors (KNN) query in time dependent road network, requires that the issued time and the arrival time of a query must be in the same time interval, which costs a long time in the preprocessing phase. To solve these problems, an Improved TD-FTT (ITD-FTT) algorithm based on dynamically selecting heuristic values was proposed. Firstly, in the preprocessing phase, the road network Gmin with the minimum cost for each time interval was created by using time functions of edges. Secondly, a parallel method of utilizing Network Voronoi Diagram (NVD) in road network Gmin was used to compute the nearest neighbors of nodes to reduce the time cost. Finally, in the query phase, the heuristic value was dynamically selected to get rid of the time interval limitation by calculating the time interval of the current arrival time of nodes. The experimental results show that in the preprocessing phase, the time cost of ITD-FTT is reduced by 70.12% compared with TD-FTT. In the query phase, the number of traversal nodes of ITD-FTT is 46.52% and 16.63% lower than TD-INE (Time Dependent Incremental Network Expansion) and TD-A (Time Dependent A star) algorithm respectively, and the response time of ITD-FTT is 47.76% and 18.24% lower than TD-INE and TD-A. The experimental results indicate that the ITD-FTT algorithm reduces the number of nodes by query expansion, decreases the time of searching the KNN results and improves the query efficiency.

Key words: time dependent road network, K Nearest Neighbors (KNN) query, Time Dependent Fast Travel Time (TD-FTT) algorithm, preprocessing, Network Voronoi Diagram (NVD)

摘要: 针对时间依赖路网中的K近邻(KNN)查询TD-FTT算法查询点发起时间与到达时间在同一时段的限制和预处理阶段计算时间代价大的问题,提出基于动态选择启发值改进的TD-FTT (ITD-FTT)算法。首先,在预处理阶段,根据各时段各边时间函数的最小值构建最小路网Gmin;然后,在路网Gmin中利用网络泰森图(NVD)并行计算节点最近邻来减少预处理阶段的计算时间;最后,在查找阶段通过计算节点到达时间所在时段,动态选择启发值来解除时间段的限制。实验结果显示,在预处理阶段ITD-FTT算法比TD-FTT算法计算时间减少了70.12%;在查询阶段ITD-FTT比TD-INE算法和TD-A算法在遍历节点个数上分别减少了46.52%和16.63%,响应时间比TD-INE算法和TD-A算法分别降低47.46%和18.24%。实验结果表明,ITD-FTT算法减少了查询扩展的节点数,降低了查找K近邻的时间,提高了查找效率。

关键词: 时间依赖路网, K近邻查询, TD-FTT算法, 预处理, 网络泰森图

CLC Number: