Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (10): 2936-2941.DOI: 10.11772/j.issn.1001-9081.2020020231

• Data science and technology • Previous Articles     Next Articles

Urban reachable region search based on time segment tree

SUN Heli, ZHANG Youyou, YANG Zhou, HE Liang, JIA Xiaolin   

  1. School of Computer Science and Technology, Xi'an Jiaotong University, Xi'an Shaanxi 710049, China
  • Received:2020-03-05 Revised:2020-03-24 Online:2020-10-10 Published:2020-04-17
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61672417).

基于时间线段树的城市可达区域搜索

孙鹤立, 张优优, 杨洲, 何亮, 贾晓琳   

  1. 西安交通大学 计算机科学与技术学院, 西安 710049
  • 通讯作者: 贾晓琳
  • 作者简介:孙鹤立(1983-),女,辽宁铁岭人,副教授,博士,CCF会员,主要研究方向:数据挖掘、城市计算;张优优(1994-),男,河南焦作人,硕士研究生,主要研究方向:城市计算、机器学习;杨洲(1991-),男,重庆人,博士研究生,主要研究方向:数据挖掘、机器学习、城市计算;何亮(1975-),男,陕西西安人,讲师,博士,CCF会员,主要研究方向:数据挖掘、机器学习;贾晓琳(1963-),女,陕西西安人,高级工程师,博士,CCF会员,主要研究方向:数据挖掘、机器学习。
  • 基金资助:
    国家自然科学基金资助项目(61672417)。

Abstract: Aiming at the problem of reachable region search problem in urban computing, a method based on time segment tree was developed. In the method, a time segment tree structure was designed to store the local reachable regions, and a dynamic adaptive search algorithm was proposed, so as to improve the efficiency and accuracy of reachable region search. The method includes four steps. Firstly, the probability time weights of road segments were constructed on the basis of road speed distribution model and the trajectory data. Then, the short-term reachable regions were queried and stored by using the hierarchical skip list algorithm. After that, an efficient index structure for the hierarchical reachable region was built by the use of the time segment tree. Finally, the iterative search in the road network was carried out by using the time segment tree index, and the reachable region set was obtained. Extensive experiments were conducted on Beijing road network and taxi trajectory datasets. The results show that the proposed method improves the efficiency and accuracy by 18.6% and 25% respectively compared with the state-of-the-art Single-location reachability Query Maximum/minimum Bounding region search (SQMB) method.

Key words: urban computing, trajectory data mining, skip list, segment tree, reachable region search

摘要: 针对城市计算中的可达区域搜索问题,提出一种基于时间线段树的搜索方法。该方法中,设计了存储局部可达区域的时间线段树结构,并提出动态自适应的可达区域搜索算法,从而提高了城市可达区域搜索的效率与准确率。该方法主要包括4个步骤:根据道路速度分布模型和轨迹数据生成道路段的概率时间权重;利用层级跳跃表算法进行短时间可达区域的查询与存储;利用时间线段树对层级可达区域建立高效的索引结构;使用时间线段树索引在道路网络中进行迭代搜索,最终输出可达区域集合。在北京市道路网络和出租车轨迹数据集上进行了大量实验,结果表明,与最新的单点上下界限区域可达查询(SQMB)方法比较,该方法在时间效率和准确率上分别提高了18.6%和25%。

关键词: 城市计算, 轨迹数据挖掘, 跳跃表, 线段树, 可达区域搜索

CLC Number: