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%。

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