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

发布时间：2024-05-19 07:03

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

【文章页数】：6 页

【部分图文】：

图1可达区域搜索框架

本文方法使用了高效的数据结构和动态的自适应搜索算法，使得城市可达区域的查询既快速又准确。整体方案框架如图1所示，主要包括4个环节：1）进行轨迹与道路的地图匹配，根据道路速度分布模型生成道路段的概率时间权重；2）利用层级跳跃表算法生成多时间粒度的局部可达区域集合，并进行短时间可达区....

图2地图匹配

首先使用地图匹配算法将轨迹数据映射到道路网络中[19]，得到各条城市道路段对应的历史轨迹。然后将历史轨迹在时间维度上进行分箱，这里以10min为间隔，根据历史轨迹计算短时间间隔内道路的平均速度和速度方差，如图2所示。通过卡方检验等数据检验方法发现，道路的速度分布满足对数正态分布....

图3层级跳跃表

若直接在层级跳跃表上进行可达区域搜索，在高频次搜索情况下，可达区域搜索仍然存在低效的问题。因此，在获得了道路的层级跳跃表之后，在其基础上构建时间线段树索引来进一步提升查询效率。如图4所示，时间线段树的基本结构是一棵二叉搜索树，它存储的是不同时间间隔的可达区域信息，每个节点包含以下....

图4时间线段树

当时间线段树构建完成后，线段树中的各个节点分别存储了不同长短时间间隔对应的可达区域（道路段）信息。以图4为例，假设层级跳跃表中存储了以下信息：从某起始路段r0出发在0～1,1～2，…，3～4min内到达的区域分别为A1、A2、A3、A4，那么时间线段树构建完成后，叶子节点3、4....

本文编号：3977766