图划分对Arc-flags算法的影响

The Influence of Graph Partitioning on Arc-flags Algorithm

最短路径计算作为导航的常用算法在移动互联网中扮演了重要角色,由于路网规模的增大和终端的不停移动,传统的串行最短路径算法已经无法满足实时性要求,因此预处理技术得到了广泛使用。Arc-flags是一个经典的基于预处理技术的最短路径算法,可以提供高效的在线最短路径查询服务。现有Arc-flags算法的研究主要集中在提升预处理时空效率和比较不同路网划分方式的优劣上,尚未见图划分对Arc-flags算法影响的深入研究。本文在真实路网上测试了不同的图划分数量和边界点数量等因素对Arc-flags算法的影响,主要包括预处理时间和空间的消耗、在线查询时间和搜索范围等方面,并根据实验结果和分析提出了合理的图划分建议(如选用好的图划分方法减少边界点数量等),为改进和使用Arc-flags算法提供指导。

The shortest path computation used in navigation system plays an important role in mobile Intemet. Due to the increase of network scale and the moving terminal, the traditional serial algorithms for the calculation of the shortest path cannot meet the real-time requirements. The offline preprocessing technology is widely used in the shortest path computation. On the other hand, the increase of graph data scale will improve online query time for the shortest path query, so graph partition technology is used to partition road network graph data. The Arc-flags algorithm is a classic shortest path algorithm based on the preprocessing and graph partition technology, which provides efficient online shortest path query. Arc-flags have two main parts, one is graph partition and flags-setting algorithm and the other one is online query algorithm. Until now, existing research on Arc-flags algorithm mainly focus on the improvement of space and time-cost of preprocessing and comparison of the pros and cons of different network partitioning methods. However, the influence of the graph partitioning for Arc-flags algorithm is not analyzed in-depth. Our paper tested and analyzed the effect of different graph partitioning technology for Arc-flags algorithm in real road networks in many aspects, such as the pre-processing time, memory consumption and online query efficiency. The real road network data includes three public data sets： American New York City Road Network, American San Francisco Bay Area Road Network and American Northeast Road Network. In order to compare the effect of different graph partition technology, one graph partition tool Metis was used. We compared Arc-flags and simple Dijkstra algorithm. Arc-flags had much better performance on online query time. Also, we compared the results of Arc-flags based on different graph partition technology, the preprocessing time and the graph partition number was linear growth while the preprocessing time increased faster than the boundary point number. The graph partition number had little effect on online query time if the number arrived a large value. The searching range had little effect on online query time if the searching range reduced to a certain extent. If so, the main effect factor was memory access efficiency and so on, not the searching range. At last, we gave some reasonable graph partitioning suggestions according to our experimental results and analysis. We should use the best graph partitioning to partition road in order to reduce the boundary point number. Our research could provide some guidance to help the improve and use of the Arc-flags algorithm for shortest path algorithm in real navigation system.