Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling

杨镇源 于 2024-04-16 发布 浏览量

Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling

原文

一、ABSTRACT

二、INTRODUCTION

  1. 距离查询的实际应用：
    • 在社交网络中，两个用户之间的距离被认为表示亲密程度，并在社交敏感搜索中使用，帮助用户找到更多相关的用户或内容或分析有影响力的人物和社区
    • 在网络图中，网页之间的距离是相关性的指标之一，并在上下文感知搜索中使用，为与当前访问的网页更相关的网页提供更高的排名
    • 在链接数据上进行前k个关键字查询
    • 在代谢网络中发现化合物之间的最佳路径
    • 在计算机网络中管理资源
  2. 传统方法及其瓶颈：
    • BFS或Dijkstra计算距离太慢，不能满足低延时
    • 事先计算所有顶点对之间的距离并将其存储在索引中，处理时间和索引大小是二次的，非常庞大不可接受
  3. 道路可分为道路网络和复杂网络：
    • 道路网络研究已经取得了很大成功。现在，对美国完整道路网络进行的距离查询可以在不到1微秒的时间内处理完成
    • 复杂网络上回答距离查询仍然是一个极具挑战性的问题

2.1 Our Contributions

论文中的方法可以处理有向/加权图，但为了方便说明，在接下来的内容中，假设图是无向、无权的

Def 2-hop cover:$\forall vertex\ u$，令$C(u)$为候选点集（可称为地标集），使得$C(u)$和$C(v)$中至少有一个公共的顶点$w$，这个公共的顶点$w$位于$u,v$的最短路径上。换句话说，从$u$到$v$的最短路径至少会“经过”（即在某处“跳过”）它们的共同地标顶点。

使用两跳覆盖进行查询:

  1. 对于图中每个顶点$u$以及一个顶点$w\in C(u)$，我们计算它们间的距离$d_G(u,w)$，因此得到集合$L(u)={(w,d_G(u,w)}_{w\in C(u)}$
  2. 当需要查询两个顶点$s$和$t$之间的最短路径长度时，我们找到$s$和$t$的地标集的公共顶点$w$，使用以下公式计算距离;
\[d_G(s,t)=min\{\delta_{ws}+\delta_{wt}|(w,\delta_{ws})\in L(s),(w,\delta_{wt})\in L(t)\}\]

论文中基于以上方法，提出了pruned landmark labeling

在执行广度优先搜索（BFS）时，如果在搜索队列中已经存在一个顶点$w$，它通过当前源点$v$可以到达，并且$v$到$w$的距离加上$w$到当前考虑的顶点$u$的距离等于$v$到$u$的距离，则顶点$u$可以被修剪，即不需要再从$u$出发继续BFS

具体来说，如果在BFS过程中遇到顶点$u$，并且存在一个已经被访问的顶点$w$，满足$d_G(v,u)=d_G(v,w)+d_G(w,u)$，那么可以确定通过$w$的路径已经是$v$到$u$的最短路径，因此可以修剪$u$，跳过对$u$的进一步搜索

然后使用位运算同时执行多个BFS过程，进一步提高了算法的处理速度

三、RELATED WORK

3.1 Exact Methods

有效地找到小的2跳覆盖是一个具有挑战性且长期存在的问题

提到了一些方法，如层次化中心地标标记（hierarchical hub labeling），高速公路中心标记（highway-centric labeling）以及基于树分解的方法

3.2 Approximate Methods

主要方法是基于地标的方法。这些方法的基本思想是选择一个顶点子集$L$作为地标，并预先计算每个地标$l\in L$和所有顶点$u\in V$之间的距离$d_G(l,u)$。当查询两个顶点$u$和$v$之间的距离时，我们会回答在地标$l\in L$上的最小值$d_G(u,l)+d_G(l,v)$作为一个估计。通常，每个查询的精度取决于实际最短路径是否经过地标附近。因此，通过选择中心顶点作为地标，估计的准确性比随机选择地标要好得多。然而，对于距离较近的顶点对，精度仍然远远低于平均水平，因为它们之间的最短路径长度较小，并且不太可能经过附近的地标

提到了新技术改进了上述方法，但是查询时间增加

四、PRELIMINARIES

图：$G(V,E)$

节点数：$n$

边数：$m$

$v$在图中的邻点：$N_G(v)$

$u,v$间距离：$d_G(u,v)$

$u,v$最段路上所有节点集合：$P_G(u,v)$

2-hop cover：$\forall vertex\ u$，计算标签集$L(u)={(w,d_G(w,u)}_{w\in C(u)}$，作为索引，距离查询$s,t$：

\[QUERY(s,t,L)=min\{\delta_{vs}+\delta_{vt}|(v,\delta_{vs})\in L(s),(v,\delta_{vt}\in L(t)\}\]

如果$L(s)$和$L(t)$没有公共节点，那么$QUERY(s,t,L)=\infty$

五、ALGORITHM DESCRIPTION

5.1 Naive Landmark Labeling

（暴力方法）

  1. 初始化索引，首先初始化空索引$L_0(u)=\emptyset,\forall u\in V$

  2. 然后按照顶点顺序$v_1,v_2,…,v_n$，从每个顶点进行一次BFS

  3. 对于第$k$次BFS，只要从顶点$v_k$开始，每个在BFS中到达的顶点$u$，将$(v_k,d_G(v_k,u))$添加到$u$的标签中，即$L_k(u)=L_{k-1}(u)\cup {(v_k,d_G(v_k,u))}$

  4. 完成所有顶点的BFS后，得到的索引$L_n$即为最终索引，通过$QUERY(s,t,L_n)$能得到$d_G(s,t)$

5.2 Pruned Landmark Labeling

剪枝

假设已知$L_{k-1}’$，下一步从$v_k$开始BFS以得到$L_k’$；假设现在到达$u$，且距离为$\delta$

若$QUERY(v_k,u,L_{k-1}’)\leq \delta$，那么将$u$剪枝；否则$L_k’(u)=L_{k-1}’(u)\cup{(v_k,\delta)}$

5.3 Proof of Correntness

证明上述改进方法计算了正确的2跳覆盖索引，即证明：

\[QUERY(s,t,L'_k)=QUERY(s,t,L_k)\]

归纳法

5.4 Vertex Ordering Strategies

按照$v_1,v_2,…,v_n$的顺序进行剪枝广度优先搜索，节点搜索的顺序对方法的性能比较重要

应该首先选择中心顶点，即许多最短路径经过这些顶点。由于我们希望尽可能多地剪枝后续的广度优先搜索，我们希望尽可能多地通过较早的广度优先搜索覆盖更多的顶点对。也就是说，较早的标签应该为尽可能多的顶点对提供正确的距离，因此较早的顶点应该是许多最短路径经过的顶点

提出三种方法作对比：

Efficient Implementation / Theoretical Properties

介绍了代码实现细节以及加速查询的细节，在此略过。

六、BIT-PARALLEL LABELING

为了进一步加速预处理和查询过程，提出了一种优化方法，该方法利用位级并行性。位级并行方法是指在同一个字中对不同的位执行不同的计算，以利用计算机可以同时对一个字进行位操作的事实。在当代的计算机中，一个字的长度通常为32位或64位。

在本章节，用$b$表示计算机一个字中的位数，并假设对长度为$b$的位向量进行位操作可以在$O(1)$时间内完成。此处提出了一种算法，可以同时从$b+1$个根节点在$O(m)$时间内执行BFS并计算标签。此外，还提出了一种方法，可以通过这$b+1$个节点中的任意一个在$O(1)$时间内回答任意一对顶点之间的距离查询。

之后在Introducing to Pruned Labeling中描述了如何将位级并行标记方法与剪枝标记方法结合起来，以提高算法的整体性能。通过在初期进行不剪枝的位级并行BFS，算法能够快速覆盖大量的顶点对，然后利用剪枝技术减少不必要的计算。

七、VARIANTS AND EXTENSIONS

该方法可扩展至以下场景：

…展示实验，体现提出方法的优越性

八、CONCLUSIONS

提出了一种新颖而高效的方法，用于在大型图上进行确切的最短路径距离查询。

算法从所有顶点进行带有剪枝的广度优先搜索（BFS）。尽管算法简单，但剪枝出人意料地减少了搜索空间和标记数量，从而实现了快速的预处理时间、小的索引尺寸和快速的查询时间。

提出了另一种利用位级并行性的标记方案，它可以很容易地与剪枝标记方法结合使用，以进一步提高性能。在各种类型的大规模现实世界网络上进行的广泛实验结果证明了我们方法的效率和鲁棒性