EN中文

Journal of Geo-information Science >

2016 , Vol. 18 >Issue 11: 1456 - 1464

DOI: https://doi.org/10.3724/SP.J.1047.2016.01456

The Influence of Graph Partitioning on Arc-flags Algorithm

  • LIU Huimin , 1, 2 ,
  • SUN Guangzhong 1, 2 ,
  • ZHOU Yinghua , 3, *
Expand
  • 1. School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China
  • 2. National High Performance Computing Center at Hefei, Hefei 230027, China
  • 3. Network Information Center of University of Science and Technology of China, Hefei 230026, China
*Corresponding author: ZHOU Yinghua, E-mail:

Received date: 2016-07-21

  Request revised date: 2016-09-30

  Online published: 2016-11-20

Copyright

《地球信息科学学报》编辑部 所有
Fold

Abstract

The shortest path computation used in navigation system plays an important role in mobile Internet. 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.

Key words： Arc-flags; algorithm analysis; graph partitioning; shortest path; preprocessing

Cite this article

LIU Huimin , SUN Guangzhong , ZHOU Yinghua . The Influence of Graph Partitioning on Arc-flags Algorithm[J]. Journal of Geo-information Science, 2016 , 18(11) : 1456 -1464 . DOI: 10.3724/SP.J.1047.2016.01456

1 引言

随着路网的扩大和移动终端的大量使用,路径查询算法要求更高的实时性,原来的串行算法已不能有效地解决路网中最短路径查询的效率问题。目前的研究主要集中在通过离线预处理方式提前进行大量辅助计算,以获得线上的快速最短路径查询响应。2012年的SIGSpatial GIS会议上,微软公司的Renate F. Werneck应邀作Real-world route planning in Bing Map主题报告,分析了路网路径计算的研究进展,并将路网路径计算划分为Metric-independent preprocessing、Metric customization和Query optimization 3个步骤[1],贴近实际地图应用,其中内容包括了对路网上最短路径问题的讨论与研究。图划分[2]是一种图数据分割技术,广泛地应用在分布式计算等领域,使用图划分进行抽象为图数据划分能够使得集群高效处理作业[3]。图数据规模的增大导致了最短路径查询时间增加,所以考虑利用图划分技术来划分路网图数据[4]。
Arc-flags是经典的基于预处理技术并结合图划分来解决路网最短路径查询问题的算法。在Arc-flags算法的相关介绍研究中,文献[5]首次提出了对边设置标志位的概念,通过在边上设置导航信息减少最短路径搜索范围,并对在线查询加速效果进行了测试。文献[6]主要讨论设置标志位的方法,在原始方法的基础上提出通过区域间边界点在逆向图扩展最短路径设置标志位的新算法,也是本文中采用的标志位设置算法[6]。文献[7]主要研究了不同的路网分割方式对在线查询的加速效果的影响,经实验表明,使用Metis和Kd树划分路网数据相比于网格划分、四叉树划分能提供更好的在线查询性能[8-9],其中Metis是流行的标准图划分工具,采用多层图划分算法更高效[10-14]。文献[15]-[17]主要对Arc-flags算法进行改进,应用在动态路网中,使Arc-flags算法更好地适应当前的复杂路网。
从上面的叙述可以看出,现有的研究主要集中在提升标志位设置算法效率和比较不同路网划分方式上,并没有针对标准图划分对Arc-flags算法的影响进行过专门深入的分析讨论,本文主要研究真实路网中标准图划分对基于预处理技术的最短路径算法Arc-flags算法性能的影响,使用标准图划分工具Metis划分路网,详细描述Arc-flags算法的思想、内容及实现方式,针对真实路网数据,测试不同图划分数量对预处理时间空间消耗和在线查询时间的影响,并根据实验结果和分析提出合理的图划分建议,为改进和使用Arc-flags算法提供指导。

2 Arc-flags算法

Arc-flags算法是一种基于预处理技术的最短路径求解算法,通过离线阶段的预处理过程获得在线查询阶段高效率的最短路径查询。算法的思想来源于生活：当你有一个明确的目的点,在道路上向目的点行进时,遇到一个路口,一般会看到一个指示牌,指示该路口的道路通向的各自目的地,选择通向你的目的点的道路继续走即可。Arc-flag算法根据这一思想设置道路指示,通过对路网中每条边附加额外的指示信息减少搜索的范围,提升最短路径查询速度。设置导航信息时,如果将图中每个点都作为目的点进行预处理,则在标记指示信息时占用太大内存,需对图数据进行划分,以更大范围地表示目的地,减少预处理消耗,即图的划分技术。
Arc-flags算法主要分为2部分：① 预处理阶段的图划分和标志位设置算法,该算法为路网数据中每条边设置导航信息即标志位;② 在线查询算法,使用改造的Dijkstra[18]算法提供在线查询服务。

2.1 图划分和标志位设置算法

对于有向图 G = V , E ,V为顶点的集合, V = n 为顶点的个数,E为边的集合, E ⊆ V × V ,|E|=m为边的个数,其权值为we。e(vi,vj)表示连接从节点vi到vj的边,边不经过其他节点, i ≠ j 。路网划分为k个不相交的区域R1,R2,…,Rk,每个区域是连通的,图 G 中每个点都属于一个区域Ri,且在实际应用中可以很方便地得到该节点所属区域。为边e(u,v)设置一个k位的标志变量flag(u,v),初始时将其所在区域对应的标志位设置为1,然后计算每条边的flag：从节点u开始,经过边e(u,v)和节点v,存在到达区域Ri的最短路径,则将flag(u,v)的第i位设置为1,否则保持不变。共有m条边,所以一共有m×k个不同标志。
在设置标记位时,为了平衡预处理资源消耗和查询效率,需要把图划分为若干个区域。图划分的区域个数和方法对Arc-flags算法效率影响较大：如果把每个点作为一个区域,则需要保存m×n位标志信息,并对每一个节点扩展最短路径树,需要消耗大量的时间和空间;如果整个图作为一个区域,则相当于没有设置导航信息,对在线查询没有帮助;如果在中间状态,把图划分为k个区域,则k的选取就需要进行研究,平衡预处理的资源消耗并达到在线查询的效率要求。
图划分就是将V划分为k个子集V1, V 2,…, Vk,对于i, j = 1, 2,…, n,满足i≠ j 时,Vi ∩Vj = ϕ,且∪Vi = V,这叫做图G 的k-路划分。每个子集Vi 称为一个划分域。划分的边割代价定义如式（1）所示。
cut G = ∑ w e （1）
式中： F = { a , b ∈ E , a ∈ V i ⋀ b ∈ V j ⋀ i ≠ j } 。图划分的目标就是将图划分为k个划分域后,获得的边割最小。不平衡函数的定义如式（2）所示。
ub G , R = max v i ∈ R ∑ w u W k （2）
式中：W是图G中所有顶点的权值和,由于对G中的顶点不设权值,所以默认为1,对一个图G的划分R,如果ub(G, R)≤(1+ε),其中ε是不平衡容许度,这说明在容许度为ε的情况下划分R是平衡的。ε一般取0.03。
计算图G的一个k路划分,在满足不平衡条件的前提下,使得划分的边割代价最小。即对任意0≤ε,在满足ub(G,R)≤(1+ε)条件下,使cut(G)最小。
本文不对图划分方法进行研究,只使用成熟的图划分工具Metis进行标准图划分。Metis采用多层图划分算法,可以对大规模的图数据产生高质量的划分,而且运行速度快,这和划分大规模路网数据的需求相一致。在Arc-flags算法的预处理过程中,设置标志位时,需要扩展区域边界节点的最短路径树,这样如果边界节点数量越少,需要扩展最短路径树的计算就越少,效率也就越高,这和标准图划分最小化边割的优化目标相一致。故使用Metis可以产生良好的图划分结果,获得更好的预处理效果。Schilling等[5]的研究也证明相较于网格、四叉树等划分图的方法,使用Metis图划分工具划分图在Arc-flags算法中取得了较好的效果。
一种朴素的计算标志位的方法包括：① 将图G(V,E)分为k个区域并获取反向图Gr;② 初始化时,将所有边的flag所有位设置为0;③ 每个区域Ri中包含边的flag的第i位设为1;④ 分别以每个区域Ri中的每个含有非该区域入边的边界顶点v为源点,在反向图Gr中求解v的单源最短路径树。将最短路径树中每条边对应的图G中的边的flag的第i位设置为1。具体算法参见算法1,算法中使用Metis工具划分好的路网,划分路网时不平衡度设置为0.03。
算法1 标志位设置算法
输入：图G=(V, E)和反向图G’=(V’, E’)及划分区域R
输出：包含flag标志的图G=(V, E)
FOR each v' IN V’ DO
dist[v’] ← ∞;
FOR each v' IN V' DO
IF v' IN Ri$ THEN
k ← i;
Q ← V';
S ← Ø;
path[v'] ← 0;
dist[v'] ← 0;
WHILE! Q.IsEmpty() DO
v' ← Q.ExtractMin();
S ← Union(S,v');
flag_k(v', path(v')) ← 1;
FOR each u IN V' AND e'(v',u) IN E' DO
IF dist[u]>dist[v]+w(v',u)} THEN
dist[u] ← dist[v]+w(v',u);
path[u]← v';
RETURN {G with flags};

2.2 基于标志位的Dijkstra算法

算法1主要描述设置边的标志算法,属于Arc-flags算法中的离线预处理部分,当预处理设置好边的标志位后,需要据此提供在线查询服务,怎样利用好预处理得到的标志性信息涉及到基于标志位的Dijkstra算法（算法2）。在线查询时,如果目标节点所在区域为R_i,当Dijkstra算法扩展到某一节点v时,如果该节点和其某一后驱节点u相连的边e(v,u)的对应的标志位信息flag(v,u)第i位为1,则扩展该节点,如果为0,则说明e(v,u)一定不在任何一条通往区域R_i的最短路径上,不能沿着该边扩展此节点,在标志位信息限制搜索范围的前提下,仍按Dijkstra算法的原有方式层层扩展节点直到找到源点到目的节点的最短路径。
算法2 基于标志位的Dijkstra算法
输入：带标志位的图G=(V,E),源点s,目标节点t
输出：s到t的最短路径
FOR each v IN V DO
dist[v] ← ∞;
IF t IN Ri THEN
k ← i;
v ← s;
Q ← V;
S ← Ø;
path[v] ← 0;
dist[v] ←0;
WHILE !Q.IsEmpty() DO
v ← Q.ExtractMin();
IF v==t THEN
break;
S ← Union(S,v);
FOR each u IN V AND e(v,u) IN E DO
IF flag_k(v,u) == 1 THEN
IF dist[u]>dist[v]+w(v,u)
dist[u]←dist[v]+w(v,u);
path[u] ← v;
ELSE
continue;
RETURN path;

3 图划分对Arc-flags算法影响实验

本文在真实路网数据中测试标准图划分对Arc-flags算法的影响,并对实验数据进行分析。

3.1 实验说明

为研究图划分数量对Arc-flags算法的全面影响,本文使用实际路网数据做相关实验并朴素的Dijkstra算法做查询效率对比。
本文所使用的算法由C++编程实现,其中Arc-flags算法包含了预处理阶段的标志位设置算法和基于标志位的Dijkstra算法。实验系统为64位Windows 7,基于x64处理器。实验硬件环境为Intel Core i5-4460 Cpu 3.20 GHz,内存为16 GB。
本实验所使用的数据为真实的美国纽约市路网、美国旧金山湾区路网和美国东北部地区路网,数据来源于“9th DIMACS Implementation Challenge - Shortest Paths”,是公开的数据集。每个图数据共包含2个数据文件,“*.gr”包含路网抽象的图数据中所有连接节点的边和代表节点之间路径距离的边的权重值,“*.co”文件包含了图中节点在现实世界中对应的经纬度坐标。为方便使用,本实验对数据进行了预处理,在该数据中,某些边的权重值小于根据坐标计算得到的2点间的直线距离,这是不合理的,将这些权重值调整为对应的欧式距离,具体数据详见表1。在后面的部分叙述中,部分地方会以“NY”指代美国纽约市地图,以“BAY”指代美国旧金山湾区地图,以“NE”指代美国东北部地图。
Tab. 1 Description of road network data sets

表1 路网数据说明

数据名称 节点数 边数
美国纽约路网NY 264 346 733 846
旧金山湾区路网BAY 321 270 800 172
美国东北路网NE 15 24 453 3 897 336
Schilling等[5]的研究说明相比于其他分割图数据的方法,使用Metis进行标准图划分可使Arc-flags算法取得较好的效果,而本文实验同样使用Metis对图进行标准图划分操作,不平衡度设置为0.03,其他参数设置为默认值。
本次实验中,针对朴素的Dijkstra算法和Arc-flags算法的查询阶段,均采用随机选取1000组源节点和目的节点进行最短路径查询,并计算平均用时的方法统计最短路径计算时间。
首先测试朴素的Dijkstra算法在不同路网上的性能,因为没有预处理过程,不同图划分数量对使用这2种算法进行最短路径计算没有影响,只和图数据的规模相关,表2为不同地图数据下Dijkstra算法进行一次最短路径查询的运行时间。
Tab. 2 The shortest path calculation time of Naïve Dijkstra algorithm

表2 朴素Dijkstra算法最短路径计算时间

数据名称 计算时间/ms
美国纽约路网NY 27.89
旧金山湾区路网BAY 32.78
美国东北路网NE 192.12
如表2所示,地图越大,Dijkstra算法的计算时间就越长,当节点数目从纽约地图的26万多增加到美国东北部地图150万左右时,Dijkstra算法的计算时间增加了约6倍,和不同路网中节点数量的差距接近。这是因为在更大的路网中,由于存在更多较远的点,平均每次计算最短路径,Dijkstra算法需要搜索的节点数量更多。
为了更好地对比算法的性能,排除算法实现等一些干扰因素,进一步用搜索范围来表示算法的性能,搜索范围定义为：求源节点到目的节点最短路径时,所有搜索过程中加入到S集合的节点数量和最后计算得到的最短路径上节点数量的比值。搜索范围能更好地反映算法本身搜索节点数量的大小,尽量排除一些干扰因素。表3为不同路网下朴素Dijkstra算法的搜索范围。由表3可以看到,搜索范围同样和路网规模有关,路网规模越大,搜索最短路径时需要搜索的节点范围也越大,从纽约路网到美国东北部路网,搜索范围增加了近2倍,但相比于不同路网最短路径计算的时间差距,搜索范围差距更小,没有路网节点规模增加的倍数高。
Tab. 3 The shortest path searching range ofnaïve Dijkstra algorithm

表3 朴素Dijkstra算法最短路径搜索范围

数据名称 搜索范围
美国纽约路网NY 314.89
旧金山湾区路网BAY 333.34
美国东北路网NE 649.12

3.2 预处理阶段实验及分析

因为标准图划分的优化目标是减少边界点的数量,而根据前面的分析可知,Arc-flags算法对图划分数量较为敏感,本实验首先使用高效的图划分工具Metis对路网数据进行了不同数量的标准图划分,然后在不同图划分数量下测试预处理时间和空间消耗,最后对在线最短路径查询效率进行测试。不平衡度设置仍为3%。
图划分边界点数量直接关系着预处理需要计算单源最短路径的节点数,与预处理时间相关性较大。图1展示了3个路网不同图划分数量下边界点的数量增长情况,从图1可以看出,边界点数量会随着图划分数量的增加而增加,整体上涨趋势接近线性,但边界点数量相对图划分数量增加得较慢,而且增加趋势逐步放缓,当划分数量为2000时,纽约地图边界点达到30 101个,旧金山湾区地图边界点达到24 532个,而东北部地图边界点数量达到了45 631个。从3个路网边界点数量对比情况来看,虽然旧金山湾区地图路网比纽约地图路网规模稍大,但相同划分数量下边界点数量却比纽约路网边界点数量小,这说明图划分后边界点数量并不随路网规模的增加而绝对增加,与路网本身特性相关,有些路网本身特性时候进行标准图划分。针对边割数量这个优化目标可以取得较好结果,而有些路网可能使用标准图划分工具划分后,划分质量较差,边割数量较多。而东北部地图图划分后,边割数量相对纽约和旧金山路网仍然较大,说明虽然图划分质量对边界点数量有影响,但整体而言边界点数量随着路网规模增大而增加。
Fig. 1 The boundary point number with differentnumber of graph-partitioning

图1 不同图划分数量下边界点数量

图2展示了不同图划分数量下Arc-flags算法在不同路网上的预处理时间。从图2可看出,3个地图上Arc-flags算法的预处理时间都随着图划分数量的增加而增加,整体增长趋势接近线性,但没有图划分数量增加得快,相较于边界点数量的差距,预处理时间差距更大,美国东北部地图的预处理时间和纽约地图的预处理时间相差接近10倍。另外,与图1中边界点数量对比可以明显地看出,虽然旧金山路网比纽约路网稍大,但旧金山路网的预处理时间较小,而旧金山路网边界点数量同样比纽约地图小,可以得出Arc-flags算法在不同路网预处理时间大小和图划分后边界点数量大小相一致,而和路网本身大小相关性较小的结论。
Fig. 2 The preprocessing time with differentnumber of graph-partitioning

图2 不同图划分数量预处理时间

在划分为2000块区域时,Arc-flags算法在纽约地图的预处理时间为40 min左右,而美国东北部地图路网的预处理时间达到了412 min,大约接近7 h,两者预处理时间接近10倍差距,而2个路网节点和边的规模差距都不到6倍。这从算法层面上看,预处理时需要针对每一个划分区域的边界点做单源最短路径计算,有多少边界点就需要计算多少次单源最短路径,2个地图边界点相差大约2倍,而使用Dijkstra算法计算单源最短路径的时间复杂度大约为O(n3),n为路网节点数量,所以美国东北部地图的预处理时间和纽约地图的预处理时间差距巨大。因为边界点数量也会随着路网规模增大而整体增大,所以预处理时间会随着路网规模增大而大幅增加。
不同图划分数量下预处理后辅助数据所占空间可以很方便地计算出来,辅助数据是在每条边上增加标志位信息,而标志位信息和图划分的数量有关,可以由式（3）计算出辅助信息所需的存储空间。Arc-flags算法的预处理阶段空间复杂度为O(|E||R|)。
space = E × R 8 × 1024 × 1024 MB （3）
通过式（3）计算得到如表4所示的辅助存储空间需求,表中仅列出额外所需的辅助数据存储空间,不包含存储路网数据本身信息所需的存储空间。从表4可以看出,辅助空间所占空间的大小在可接受的范围内,在美国东北部地图上,划分2048个区域后所需空间大小为929.27 MB,在存储设备越来越发达的今天,个人计算机都可以承受。从 式（3）可以看出,在路网确定的情况下,随着图划分数量线性增加,所需辅助空间也线性增加,而当图划分数量确定,随着路网边的数量线性增加,辅助空间的需求也线性增加。表5展示了不同图划分数量下Arc-flags查询阶段使用基于标志位的Dijkstra算法进行最短路径计算的查询时间。从表5可看出,相比与表2中朴素的Dijkstra算法最短路径查询时间,Arc-flags算法中使用基于标志位的Dijkstra算法的查询时间有了较大的提高。为了更好地描述Arc-flags在线查询阶段的加速效果,本文加入了图3作为说明。图3展示了不同路网中朴素的Dijkstra算法和基于标志位的Dijkstra算法最短路径查询时间的比值,比值越大,说明Arc-flags算法在线查询效率越高。从图3可看出,随着图划分数量的增加,Arc-flags算法可以获得更好的在线查询速度,在2000个划分区域时,3个地图中基于标志位的Dijkstra算法查询时间效率都提升了30倍以上。对比3个不同规模的路网,发现在相同的图划分数量下,美国东北部路网的加速效果更好,而旧金山路网和纽约路网加速效果接近,说明加速效果和路网规模有关,路网越大,加速效果越好,但对比加速效果的差距和路网规模的差距可以看出,加速效果的增长相对于路网规模的增加较小。另外,在纽约市路网和旧金山湾区路网中,划分数量从1000增加到2000时,2个查询算法的时间效率没有得到提升,甚至有所下降,而美国东北部路网在划分数量在大于1200时查询效率提升也很有限,说明当划分数量增加到一定程度时,即使划分数量继续增长,查询效率提升也很小。
Tab. 4 Space size with different number of graph-partitioning

表4 不同图划分数量辅助空间需求大小

空间/MB 划分数量
200 400 600 800 1000 1200 1400 1600 1800 2000
美国纽约路网NY 17.50 34.99 52.49 69.99 87.48 104.98 122.47 139.97 157.47 174.96
旧金山湾区路网BAY 19.08 38.16 57.23 76.31 95.39 114.47 133.54 152.62 171.70 190.78
美国东北路网NE 92.93 185.85 278.78 371.71 464.63 557.56 650.49 743.42 836.34 929.27
Tab. 5 Algorithm query time with different number of graph-partitioning

表5 不同图划分数量Arc-flags算法查询时间

时间/ms 划分数量
200 400 600 800 1000 1200 1400 1600 1800 2000
美国纽约路网NY 1.40 1.11 1.07 1.00 0.92 0.92 0.92 0.91 0.92 0.90
旧金山湾区路网BAY 1.53 1.33 1.20 1.14 1.12 1.09 1.08 1.10 1.04 1.04
美国东北路网NE 8.12 6.82 6.26 6.16 6.16 5.58 5.55 5.35 5.57 5.30
Fig. 3 Algorithm time acceleration with differentnumber of graph-partitioning

图3 不同图划分数量下Arc-flags算法时间加速

图4和表6展示了Arc-flags算法中搜索范围的情况,图4中曲线的值表示朴素的Dijkstra算法搜索范围和基于标志位的Dijkstra算法搜索范围的比值,比值越大,说明Arc-flags算法搜索范围越小,在线查询效率越高。可以看到Arc-flags算法在线查询阶段对比朴素的Dijkstra算法,搜索范围的缩减效果相较于时间加速效果更好,随着划分数量的增加而搜索的范围更小,而且正在趋势相对于时间加速更明显。另外可以看出,当图划分数量增长到大约1600时,3个地图上基于标志位的Dijkstra算法搜索范围随着划分数量的再次提升缩减效果有限,对比图3可以看出,搜索范围的缩减效果比查询时间的提升更有效,说明当搜索范围减少到一定程度时,影响查询速度的主要因素不再是搜索范围,而是其他限制条件,如内存访问效率等。
Fig. 4 Ratio of query range before and after using Arc-flags with different number of graph-partitioning

图4 不同图划分数量Arc-flags使用前后搜索范围比值”

将图2-4结合来看,图2中随着划分数量线性增加,预处理时间也接近线性增加。而图3中,当划分数量增加到一定程度时,时间效率基本不再提升,即预处理时间的增加和效率提升不成正比,每获得一分增加的效率,就要付出更多的预处理时间。图4中也是同样的情况,当划分数量增加到一定程度,虽然付出了更多的预处理时间,但搜索过程中搜索范围不能有效地减少。

3.3 实验总结

从3.2节的实验结果和分析可看出,Arc-flags算法在路网最短距离查询中相对于传统串行算法提升很多,在不同的路网数据下相较于朴素的Dijkstra算法查询时间都有很大的减少,当然这是在牺牲了一部分存储空间和预处理时间得到的。对比Arc-flags在不同路网规模下的表现,可看到该算法对辅助存储空间需求不大,较大的图划分数量下辅助空间的需求仍可以很容易得到满足。在Arc-flags算法中,图划分数量和边界点数量对预处理时间影响较大,图划分数量越多预处理时间越长,基本成线性增长关系,而边界点数量对预处理时间影响更大,随着图划分后边界点数量的增长,预处理时间增长幅度更大。另外,相较于边界点数量,路网规模对预处理时间影响更小,这和图划分的质量有关,也和路网本身特性有关,有时虽然路网规模稍大,但图划分后边界点数量较少时,预处理时间仍会较小。从数据中可以看到,当图划分数量较大时,即使划分数量继续增长,在线查询效率提升效果和搜索范围缩减效果不明显,这说明达到一定划分个数后,更多的划分区域对效率提升不再有帮助,而此时预处理时间仍然继续增加,和效率提升不成正比。从搜索范围的缩减情况看,其缩减效果比查询时间的减少更有效,说明当搜索范围减少到一定程度时,影响查询速度的主要因素不再是搜索范围,而是其他限制条件,如内存访问效率等。
Tab. 6 Arc-flags query range with different number of graph-partitioning

表6 不同图划分数量Arc-flags算法搜索范围

数据 划分数量
200 400 600 800 1000 1200 1400 1600 1800 2000
美国纽约路网 9.45 6 5.29 4.28 3.51 3.4 3.25 2.87 2.84 2.69
旧金山湾区路网 7.77 5.49 4.15 3.37 3.05 2.91 2.51 2.38 2.29 2.21
美国东北路网 16.46 10.84 8.22 7.03 6.43 5.49 4.96 4.28 4.31 4.14

4 对Arc-flags算法的图划分建议

根据上述实验结果和分析,针对使用基于标准图划分的Arc-flags算法提供路网最短路径查询的服务提供商,本文提出如下建议：
（1）图划分数量引起的辅助存储空间开销在实际应用中可以不考虑,因为这部分开销不大。虽然路网规模较大和图划分数量较高时,会导致使用较大的辅助内存需求,但以如今内存的容量和价格很容易满足需求。
（2）预处理阶段图划分数量可以通过实验选择。从本文实验数据可以看出,在路网规模较大时,如果划分数量过多则预处理时间较长,美国东北部路网在图划分数量为2000时预处理时间接近7 h。另外在线查询时间效率的提升在图划分数量为1200左右时达到瓶颈,而搜索范围的缩减也在1600左右时达到瓶颈。当图划分数量更大时,预处理时间虽然持续增加,但效率提升有限,所以建议预处理阶段图划分数量选择1400左右,这样可以在预处理时间和在线查询效率获得平衡。
（3）尽可能使用可获得较高质量的图划分工具划分路网。从实验结果可以看出,尽管旧金山路网规模比纽约路网规模更大,但由于旧金山路网的图划分质量更高,可获得更少的边界点数量,导致预处理时间也相对纽约路网较小,而2个路网的在线查询时间加速情况基本一致,所以如果能使用更高质量的图划分工具划分路网,减少边界点数量,则可在消耗更少预处理时间的同时,仍获得较好的查询时间加速。

5 结论

本文研究了图划分对路网最短路径计算中的经典算法Arc-flags算法的影响。首先,描述了Arc-flags算法,并给出了具体的算法描述。然后,使用真实的路网进行了相关实验,实验中使用经典的图划分工具Metis对路网数据进行划分,研究了不同图划分数量下预处理时间和空间的增长趋势。最后,分析了不同图划分数量下在线查询算法的查询及相对于串行算法的加速情况,通过研究分析给出了合理的图划分建议。
今后将进一步改进Arc-flags算法,以获得更好的在线查询速度,并尝试将图划分技术更好地应用于最短路径计算中。

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
Delling D, Werneck R F.Customizable point-of-interest queries in road networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2015,27(3):686-698.We present a unified framework for dealing with exact point-of-interest (POI) queries in dynamic continental road networks within interactive applications. We show that partition-based algorithms developed for point-to-point shortest path computations can be naturally extended to handle augmented queries such as finding the closest restaurant or the best post office to stop on the way home, always ranking POIs according to a user-defined cost function. Our solution allows different trade-offs between indexing effort (time and space) and query time. Our most flexible variant allows the road network to change frequently (to account for traffic information or personalized cost functions) and the set of POIs to be specified at query time. Even in this fully dynamic scenario, our solution is fast enough for interactive applications on continental road networks.

DOI

[2]
FJ LLSTR M P-O. Algorithms for graph partitioning: A survey[M]. Linköping: Linköping University Electronic Press, 1998.

[3]
Pothen A.Graph partitioning algorithms with applications to scientific computing[J]. Parallel Numerical Algorithms, 1997,4:323-368.Identifying the parallelism in a problem by partitioning its data and tasks among the processors of a parallel computer is a fundamental issue in parallel computing. This problem can be modeled as a graph partitioning problem in which the vertices of a graph are divided into a specified number of subsets such that few edges join two vertices in different subsets. Several new graph partitioning algorithms have been developed in the past few years, and we survey some of this activity. We describe the terminology associated with graph partitioning, the complexity of computing good separators, and graphs that have good separators. We then discuss early algorithms for graph partitioning, followed by three new algorithms based on geometric, algebraic, and multilevel ideas. The algebraic algorithm relies on an eigenvector of a Laplacian matrix associated with the graph to compute the partition. The algebraic algorithm is justified by formulating graph partitioning as a quadratic assignment problem. We list several papers that describe applications of graph partitioning to parallel scientific computing and other applications. Finally we discuss the application of graph partitioning to obtain nested dissection orderings for solving sparse linear systems of equations in parallel.

DOI

[4]
Goldberg A V, Harrelson C.Computing the shortest path: A search meets graph theory[C]. Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2005:156-165.

[5]
Lauther U.An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background[J]. Geoinformation und Mobilität-von der Forschung zur praktischen Anwendung, 2004,22:219-230.Page 1. C O R P O R A TE TE C H N O LO G Y Software & Engineering Discrete OptimizationAn Extremely Fast, Exact Algorithm for Finding Shor test Paths in Static Networks withGeographical Background Ulr ich Lauther Siemens AG, München ulr ich.lauther@siemens.com

[6]
Lauther U.An experimental evaluation of point-to-point shortest path calculation on roadnetworks with precalculated edge-flags[J]. The Shortest Path Problem: Ninth DIMACS Implementation Challenge, 2006,74:19-40.We present an efficient algorithm for fast and exact calculation of shortest paths in graphs with geometrical information in nodes (coordinates), e.g. road networks. The method is based on preprocessing and therefore best suited for static graphs, i.e., graphs with fixed topology and edge costs. In the preprocessing phase, the network is divided into regions and edge flags are calculated that indicate whether an edge belongs to a shortest path into a given region. In the path calculation step, only those edges need to be investigated that carry the appropriate flag. We compared this method to a classical Dijksta implementation using USA road networks with travel times and report on speedup, preprocessing time, and memory needed to store edge flags. 1

[7]
M HRING R H, Schilling H, SCH TZ B, et al. Partitioning graphs to speedup Dijkstra's algorithm[J]. Journal of Experimental Algorithmics (JEA), 2007,11:2-8.Furthermore, we present an extension of this speed-up technique to multiple levels of partitionings. With this multi-level variant, the same speed-up factors can be achieved with smaller space requirements. It can therefore be seen as a compression of the precomputed data that conserves the correctness of the computed shortest paths.

DOI

[8]
Karypis G, Kumar V.Analysis of multilevel graph partitioning[C]. Proceedings of the 1995 ACM/IEEE conference on Supercomputing. ACM, 1995:29.

[9]
Bentley J L.Multidimensional binary search trees used for associative searching[J]. Communications of the ACM, 1975,18(9):509-517.

[10]
Kernighan B W, Lin S.An efficient heuristic procedure for partitioning graphs[J]. Bell system technical journal, 1970,49(2):291-307.

[11]
Barnard S T, Simon H D.Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems[J]. Concurrency: Practice and Experience, 1994,6(2):101-117.Abstract If problems involving unstructured meshes are to be solved efficiently on distributed-memory parallel computers, the meshes must be partitioned and distributed across processors in a way that balances the computational load and minimizes communication. The recursive spectral bisection method (RSB) has been shown to be very effective for such partitioning problems compared to alternative methods, but RSB in its simplest form is expensive. Here a multilevel version of RSB is introduced that attains about an order-of-magnitude improvement in run time on typical examples.

DOI

[12]
Goehring T, Saad Y.Heuristic algorithms for automatic graph partitioning[R]. Technical report, Department of Computer Science, University of Minnesota, Minneapolis, 1994.

[13]
Hendrickson B, Leland R W.A Multi-Level Algorithm For Partitioning Graphs[C]. Proceedings of the 1995 ACM/IEEE conference on Supercomputing. ACM, 1995:99:108.

[14]
Karypis G, Kumar V.Analysis of multilevel graph partitioning[C]. Proceedings of the 1995 ACM/IEEE conference on Supercomputing. ACM, 1995:29-38.

[15]
D'angelo G, Frigioni, Vitale C. Dynamic arc-flags in road networks[M]. Experimental Algorithms. Springer. 2011: 88-99.

[16]
Berrettini E, D'Angelo G, Delling D. Arc-flags in dynamic graphs[C]. OASIcs-OpenAccess Series in Informatics. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2009.

[17]
D' angelo G, D' emidio M, Frigioni D, et al. Fully dynamic maintenance of arc-flags in road networks[C]. 11th International Symposium on Experimental Algorithms (SEA2012), June 2012, Bordeaux, France. Springer, 2012:135-147.

[18]
Dijkstra E W.A note on two problems in connexion with graphs[J]. Numerische mathematic, 1959,1(1):269-271.

Options
Outlines

/

〈 〉