PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Takuya Akiba, Yoichi Iwata, Yuichi Yoshida

arXiv:1304.4661v1cs.DScs.DB

TL;DR

Large complex networks need exact distance queries that are much faster than BFS or Dijkstra’s algorithm without the quadratic costs of all-pairs indexing. The paper combines pruned BFS-based labeling with bit-parallel BFS, achieving exact queries and scalable indexing on networks with hundreds of millions of edges. Experiments report comparable query time and index size to prior methods, while the authors identify further index-size reduction and larger-than-memory graphs as future challenges.

  • Problem

    Large-graph distance queries require low-latency exact answers, but per-query search is slow and all-pairs indexing has quadratic preprocessing time and space.

  • Method

    The method performs BFS from every vertex with pruning during searches and adds bit-parallel labeling that performs multiple BFSs simultaneously.

  • Results

    The method handled networks with hundreds of millions of vertices, two orders of magnitude larger than prior exact-method limits, with comparable index size and query time.

  • Takeaways & Limitations

    Pruned labeling and bit-level parallelism provide efficient and robust exact distance queries across large real-world networks.

  • Takeaways & Limitations

    Reducing index size remains an important next research issue, and even larger graphs may require indices or graphs that do not fit in main memory.

Abstract

from arXiv · show

We propose a new exact method for shortest-path distance queries on large-scale networks. Our method precomputes distance labels for vertices by performing a breadth-first search from every vertex. Seemingly too obvious and too inefficient at first glance, the key ingredient introduced here is pruning during breadth-first searches. While we can still answer the correct distance for any pair of vertices from the labels, it surprisingly reduces the search space and sizes of labels. Moreover, we show that we can perform 32 or 64 breadth-first searches simultaneously exploiting bitwise operations. We experimentally demonstrate that the combination of these two techniques is efficient and robust on various kinds of large-scale real-world networks. In particular, our method can handle social networks and web graphs with hundreds of millions of edges, which are two orders of magnitude larger than the limits of previous exact methods, with comparable query time to those of previous methods.

1. INTRODUCTION

Exact distance queries on complex networks require microsecond-scale responses without the quadratic preprocessing and index costs of all-pairs methods. The paper introduces pruned landmark labeling and bit-parallel BFS, achieving scalable exact queries on large real-world graphs.

  • Motivation: Microsecond-scale distance queries are needed for real-time applications that rank items using distances between many vertex pairs.BFS and Dijkstra’s algorithm can take more than a second on large graphs.
  • Motivation: All-pairs distance indexing answers queries instantly but requires quadratic preprocessing time and space.The paper seeks a more moderate approach between per-query graph search and all-pairs indexing.
  • Motivation: Complex-network methods remain difficult to scale, with prior exact approaches taking thousands or tens of thousands of seconds to index graphs with millions of edges.Road-network methods exploit structures that differ substantially from those of complex networks.
  • Pruned landmark labeling: The method builds a 2-hop cover by storing landmark-distance pairs in vertex labels, so query distance is the minimum sum over shared label vertices.A shared vertex lies on a shortest path for each queried pair.
  • Pruned landmark labeling: Pruning during BFS avoids visiting vertices whose distances are already certified through previously processed vertices, reducing the search space and label sizes.The naive all-vertex BFS approach would require O(nm) preprocessing time and O(n^2) index space.
  • Bit-parallel labeling: Bit-parallel labeling performs BFSs from b + 1 vertices simultaneously in O(m) time, where register width b is typically 32 or 64 bits.This reduces computational complexity by a factor of b + 1 and can be combined with pruning.
  • Results: Indexing took only tens of seconds for networks with millions of edges, while previous methods required at least thousands of seconds or more than one day.The method also handled networks with hundreds of millions of edges, two orders of magnitude larger than prior exact-method experiments.

2. RELATED WORK

Prior exact methods for complex networks include 2-hop-cover labeling, hierarchical hub labeling, highway-centric labeling, and tree decompositions. Approximate landmark methods improve scalability but can sacrifice close-pair precision or query speed.

  • Exact methods: Many exact distance-query methods for complex networks use the 2-hop-cover idea, whose efficient construction with small covers remains challenging.Hierarchical hub labeling and highway-centric labeling are examples of related approaches.
  • Exact methods: Highway-centric labeling combines label distances with distances in a spanning tree to estimate shortest-path distances through labeled endpoints.It first computes a spanning tree used as a highway.
  • Exact methods: Tree-decomposition methods heuristically decompose graphs and store shortest-distance matrices for bags, with smaller largest bags making processing easier.A tree decomposition associates graph-vertex sets, called bags, with a tree.
  • Approximate methods: Approximate methods improve scalability but may answer queries in milliseconds or have low precision for close vertex pairs.The latter limitation matters when distances distinguish closely related items.
  • Approximate methods: Landmark approximations estimate distance by minimizing sums through selected landmarks, with central landmarks generally improving accuracy.Close shortest paths are less likely to pass near landmarks, so their precision is worse than average.
  • Approximate methods: Tree-based path refinements can significantly improve approximation accuracy, but query time becomes up to three orders of magnitude slower.These methods store shortest-path trees rooted at landmarks and search candidate paths for loops or shortcuts.

3. PRELIMINARIES

The paper defines graph distances, shortest-path vertices, and the indexing problem, then presents distance labeling as a 2-hop-cover framework for exact queries. Labels support query evaluation by combining matching stored vertices.

  • Graph notation: The graph is G = (V, E), with n = |V| vertices and m = |E| edges, and NG(v) denotes the neighbors of v.The notation is used throughout the paper’s graph formulation.
  • Graph notation: Distance dG(u, v) is the graph metric between vertices and is defined as ∞ when the vertices are disconnected.Graph distances satisfy the triangle inequalities.
  • Shortest paths: PG(s, t) contains exactly the vertices v satisfying dG(s, v) + dG(v, t) = dG(s, t), namely vertices on shortest paths between s and t.This set identifies vertices that can serve as shortest-path intermediates.
  • Problem definition: The studied problem is to construct an index that efficiently answers the distance between any arbitrary pair of vertices.The exposition mainly assumes undirected, unweighted graphs, while extensions cover directed and weighted graphs.
  • Labels and 2-hop cover: A 2-hop-cover labeling method stores, for each vertex v, pairs (u, δuv) where δuv = dG(u, v).The collection of all labels forms the index.
  • Labels and 2-hop cover: Query(s, t, L) returns the minimum sum of distances for a shared label vertex and equals dG(s, t) for every pair when L is a distance-aware 2-hop cover.If the two labels share no vertex, the query value is ∞.
  • Labels and 2-hop cover: Sorting label pairs by vertex allows Query(s, t, L) to be computed in O(|L(s)| + |L(t)|) time using a merge-join-like algorithm.The query scans the two sorted labels to find shared vertices and their minimum distance sum.

4. ALGORITHM DESCRIPTION

The algorithm replaces exhaustive labeling with pruned breadth-first searches, retaining exact distances while reducing later search. It incrementally builds a 2-hop-cover index from vertex-ordered searches.

  • Naive method: The naive index runs a BFS from every vertex and stores distances to all reached vertices.This produces a correct 2-hop cover but is inefficient as a direct implementation.
  • Preprocessing: The preprocessing algorithm performs pruned BFSs in vertex order and updates one index with labels obtained from each search.Algorithm 1 describes a pruned BFS, while Algorithm 2 computes the complete 2-hop-cover index.
  • Pruned BFS: Pruning stops expansion at vertex u when the existing index already answers Query(vk, u) with distance at most the BFS distance δ.The algorithm then omits the new label and traversing edges from u; otherwise it adds (vk, δ) and continues normally.
  • Pruning effect: As more BFSs are performed, the search space becomes progressively smaller because already-certified distances trigger pruning.In the example, vertex 6 is pruned when the existing query gives distance 3, equal to its BFS distance.

4.3 Proof of Correctness

The paper proves that pruned landmark labeling preserves the query answers of the naive index at every preprocessing stage. Consequently, the final index answers exact shortest-path distances for every vertex pair.

  • Theorem 4.1: For every 0 ≤ k ≤ n, the pruned index L′k produces the same query result as the unpruned index Lk.The theorem is established by mathematical induction on k.
  • Proof strategy: The proof identifies the earliest common landmark attaining the naive query minimum and shows its labels survive pruning.The argument is symmetric for the two queried vertices.
  • Proof strategy: Earlier landmarks cannot lie on the relevant shortest-path prefix for a later landmark, because their labels would contradict the assumed minimality of the later landmark.The contradiction uses the triangle inequality and existing labels at both query vertices.
  • Proof strategy: Every vertex on the relevant shortest-path prefix is therefore visited without pruning and receives the later landmark label.This establishes that the required common landmark remains available in the pruned index.
  • Corollary 4.1: At k = n, the method is an exact distance-querying method: Query(s, t, L′n) = dG(s, t) for every pair.This is the stated corollary of the theorem.

4.4 Vertex Ordering Strategies

The order of BFS roots is freely selectable but materially affects performance. The proposed strategies prioritize vertices expected to cover many shortest-path pairs early, enabling more later pruning.

  • Ordering rationale: The vertex order is flexible, but the paper reports that it is crucial for performance.The effect is examined experimentally in Section 7.3.4.
  • Ordering rationale: Central vertices are selected first because many shortest paths pass through them, allowing earlier labels to cover more vertex pairs.Broader early coverage is intended to maximize pruning in subsequent BFSs.
  • Strategies: The ordering problem resembles landmark selection in approximate distance methods, where useful landmarks lie on or near many shortest paths.The paper uses this prior connection to motivate its ordering strategies.
  • Strategies: Random ordering is a baseline, Degree orders vertices by decreasing degree, and Closeness orders them by estimated closeness centrality.Exact closeness for all vertices costs O(nm), so the paper approximates it by sampling vertices and computing distances.

4.5 Efficient Implementation

The implementation avoids unnecessary copying and initialization, accelerates label queries with compact arrays and lookup techniques, and reduces memory-access overhead through prefetching and cache-aware storage.

  • Initialization: Avoiding O(n) initialization per BFS is essential because the pruned search space is much smaller than the graph.Repeated full-array initialization would otherwise become the preprocessing bottleneck.
  • Query acceleration: A lookup optimization computes δwu + T[w] and returns the minimum, speeding the bottleneck preprocessing step by about twice.The table T uses compact 8-bit integers and also avoids O(n) initialization.
  • Memory locality: Manual prefetching reduces cache misses and speeds preprocessing by about 20% when the index and adjacency lists do not fit in cache.Vertices likely to be accessed soon are known from the BFS queue.
  • Data layout: Sentinel entries, separate vertex and distance arrays, and cache-line alignment streamline label scanning and storage.The sentinel lets paired label scans terminate on the same dummy vertex.

4.6 Theoretical Properties

The pruned landmark labeling method has minimal labels and theoretically exploits both central vertices and tree-like graph structure. These properties yield bounds on label size, preprocessing, storage, and query time.

  • Each stored label pair is necessary: removing any pair can make some vertex-pair distance unanswerable.
  • The method can exploit highly central vertices because landmark-based precision limits the pairs requiring additional index entries.
  • If k landmarks correctly answer (1−ε)n^2 pairs, average label size is O(k + εn).
  • For tree-width w, preprocessing takes O(wm log n + w^2n log^2 n), storage O(wn log n), and queries O(w log n).
  • Centroid decomposition recursively confines later pruned searches to smaller components, producing O(w log n) pairs per label.

5. BIT-PARALLEL LABELING

Bit-parallel labeling accelerates breadth-first-search labeling and distance queries by processing multiple roots through word-level operations. Combined with pruning, it improves preprocessing, index size, and query performance.

  • Bit-level parallelism uses word operations to perform calculations on multiple bits simultaneously, with common word lengths of 32 or 64.
  • The algorithm conducts BFSs from b + 1 roots simultaneously in O(m) time.
  • Each query scans the two bit-parallel labels and runs in O(|LBP(s)|+ |LBP(t)|) time.
  • Bitwise intersections determine whether the query distance is ˜δ −2, ˜δ −1, or ˜δ in O(1) time.
  • The combined scheme first performs t unpruned bit-parallel BFSs, then uses both bit-parallel and normal labels during pruned BFSs.
  • Experiments show that the combination improves preprocessing time, index size, and query time without requiring a finely tuned t when t is not too large.

6. VARIANTS AND EXTENSIONS

The method extends beyond distance queries and undirected unweighted graphs by supporting shortest-path reconstruction, weighted graphs, and directed graphs.

  • Shortest-Path Queries: Shortest-path reconstruction stores parent information in label tuples, allowing paths to be restored by ascending the corresponding BFS tree.
  • Weighted Graphs: Weighted graphs require pruned Dijkstra’s algorithm, while bit-parallel labeling is unavailable for weighted graphs.
  • Directed Graphs: Directed graphs use separate outgoing and incoming labels and perform pruned searches in forward and reverse directions.

7. EXPERIMENTS

Experiments on diverse real-world networks show that pruning and bit-parallel BFS make exact distance labeling scalable while preserving fast, stable queries. The method handles much larger graphs than prior exact approaches, though index size remains a potential improvement area.

  • Datasets: Experiments covered five social networks, three web graphs, and three computer networks, using smaller datasets for comparison and larger datasets for scalability.All graphs were treated as undirected and unweighted.
  • Dataset statistics: The evaluated networks generally exhibit power-law degree distributions and very small average distances, indicating small-world structure.Degree distributions were examined because vertex degree guides the Degree ordering strategy.
  • Preprocessing time and scalability: Two orders of magnitude larger graph sizes became processable: Hollywood and Indochina had millions of vertices and hundreds of millions of edges with moderate preprocessing time.Existing exact methods required thousands or tens of thousands of seconds for graphs with millions of edges.
  • Preprocessing time and scalability: Less than 1,000 seconds sufficed for the next four datasets with tens of millions of edges, while previous methods did not finish after one day or ran out of memory.For the smaller six datasets, preprocessing took at most one minute and was at least about 50 times faster for most datasets.
  • Query time: Average query time was generally measured in microseconds and never exceeded 16 microseconds, with little increase on larger networks.For almost all smaller datasets, query time was faster than previous methods and otherwise comparable.
  • Pruned BFS and labels: After 1,000 pruned BFSs, fewer than 10% of vertices received added distances, and after 10,000 BFSs, fewer than 1% did across all three datasets.A large portion of labels was computed early, and label sizes varied little across vertices, supporting stable query time.
  • Coverage and pruning: Most vertex pairs were covered early, with distant pairs covered before close pairs because shortest paths often pass through a small set of central vertices.The method exploits this coverage pattern for pruning, while landmark-based approximate methods have poorer precision for close pairs.
  • Bit-parallel BFS: Bit-parallel BFS reduced preprocessing time by two to ten times and also reduced query time, while performance remained fairly insensitive to the parameter unless it was too large.The proper parameter appeared common across different networks.

8. CONCLUSIONS

The paper presents pruned distance labeling and bit-level parallelism for exact shortest-path queries, achieving efficient and robust performance on large real-world networks while leaving still-larger graphs as future work.

  • Pruned breadth-first searches reduce search space and label sizes, enabling fast preprocessing, small indexes, and fast exact queries.The labeling algorithm combines BFS from all vertices with pruning.
  • Bit-level parallelism provides another labeling scheme that can be combined with pruning to improve performance.The scheme exploits parallel BFS operations at the bit level.
  • Extensive experiments on varied large-scale real-world networks demonstrate the methods' efficiency and robustness.
  • Hundreds of millions of vertices are supported, two orders of magnitude beyond previous methods, with comparable index size and query time.
  • Handling graphs whose indices or graph data do not fit in main memory remains future work.Planned directions include reducing index size and using disk-based or distributed implementations.
Loading 1304.4661v1…