基于R树优化的地图匹配算法

Map Matching Algorithm Based on R-tree Optimization

针对地图匹配算法中低采样率ST-matching算法运行时间长的问题,利用索引结构来加速搜索过程。采用了R树及其变种索引,以ST-matching算法为基础,改进并优化ST-matching算法。将搜索圆形区域转化为矩形区域以支持覆盖和交叉查询,利用滑动窗口优化回退问题。实验结果表明,以R树和其变种索引能在扩大搜索范围情况下,明显减少搜索时间,从而缩短算法运行时间,提高匹配系统效率。

AiIn order to solve the problem of long running time of low sampling rate ST-matching algorithm in map matching algorithm,the index structure is used to speed up the search process.The R-tree and its variant index are adopted,and the STmatching algorithm is improved and optimized based on the ST-matching algorithm.The search circular area is transformed into a rectangular area to support overlay and cross query,and the sliding window is used to optimize the fallback problem.The experimental results show that the R-tree and its variant index can obviously reduce the search time under the condition of expanding the search range,thus shorten the running time of the algorithm and improve the efficiency of the matching system.