计算机应用

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

单位：西安交通大学 计算机科学与技术学院, 西安 710049

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

基金：国家自然科学基金资助项目（61672417）。

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

来源：2020年第10期

《计算机应用》期刊编辑部

查看计算机应用杂志2020年第10期