面向时间依赖路网的空间索引方法

Spatial Index Method for Time Dependent Road Network

在兴趣点(POI)呈稀疏分布时,现有时间依赖路网中的k近邻查询方法效率较低,且无法高效支持多类型的POI查询。为此,建立基于POI分布的空间索引结构TDG。根据路径权值上、下界对预计算路径进行剪枝优化,在此基础上,提出一种索引更新策略与基于TDG的k近邻查询算法。实验结果表明,与启发式查询算法相比,该算法的扩展节点数量平均减少87.5%,查询响应时间平均缩短33%～66%。

When Points of Interest(POI) are sparsely distributed,the existing k-nearest neighbor query method in time dependent road network is inefficient and can not support multi-type POI queries efficiently.Therefore,a spatial index structure TDG based on POI distribution is established.According to the upper and lower bounds of the path weights,pruning and optimization of the predicted paths is carried out.On this basis,an index update strategy and a TDG-based k-nearest neighbor query algorithm are proposed.Experimental results show that compared with heuristic query algorithm,the average number of extended nodes of the proposed algorithm is reduced by 87.5 %,and the average response time to a query is reduced by 33 %~66 %.