Pruned Landmark Labeling Meets Vertex Centric Computation: A Surprisingly Happy Marriage!

Ruoming Jin, Zhen Peng, Wendell Wu, Feodor F. Dragan, Gagan Agrawal, Bin RenarXiv 2019 · arXiv

Abstract

Computing shortest-path distances in massive graphs is a cornerstone of network analysis. Pruned Landmark Labeling (PLL) has emerged as a state-of-the-art technique for 2-hop labeling, yet its inherently sequential nature makes it difficult to parallelize. This paper presents BVC-PLL, a novel algorithm that maps PLL to a Vertex-Centric (VC) computational model. By employing batched processing, bit-vector filtering, and SIMD vectorization, BVC-PLL achieves remarkable scalability and efficiency, outperforming the original sequential algorithm even in single-threaded execution.

Introduction

The shortest path problem is fundamental to applications ranging from social network analysis to web search. While traditional algorithms like BFS or Dijkstra are efficient for single queries, they are too slow for real-time applications on massive graphs. The 2-hop labeling approach solves this by pre-calculating distance labels for every vertex.

Table of vertex labels generated by the PLL algorithm. Each entry represents a landmark and its distance from the vertex.

As shown in the table above, a distance query then becomes a simple coordination of two small lists. Pruned Landmark Labeling (PLL) is the gold standard for constructing these labels, but its sequential dependency—where the labeling of later vertices depends on the results of earlier ones—has long hindered its parallelization on modern multi-core systems.

The Challenge of Parallelizing PLL

The primary obstacle in parallelizing PLL is its strict vertex ordering. In the standard algorithm, vertices are processed one by one as "landmarks." The pruning condition, which keeps labels small and queries fast, relies on the distances calculated from previously processed landmarks.

The incremental labeling process of PLL, showing how labels are added vertex by vertex (a -> b -> c).

This "think-like-a-landmark" approach is fundamentally at odds with the "think-like-a-vertex" paradigm of Vertex-Centric (VC) models like Pregel, which thrive on simultaneous, independent operations across all vertices.

The BVC-PLL Solution: Batched Vertex-Centric Computation

To bridge this gap, the authors propose BVC-PLL (Batched VC-PLL). This approach transforms the sequential landmark processing into a series of parallel vertex-centric iterations. Instead of processing all vertices at once or one by one, it processes vertices in batches.

The core innovations of BVC-PLL include:

  • Bit-Vector Filtering: Each vertex maintains a compact bit-vector to track which landmark labels it has already received in the current batch, drastically reducing redundant messages.
  • SIMD Vectorization: The authors optimized the "distance check" kernel using AVX-512 instructions, allowing the CPU to process multiple distance comparisons simultaneously.
  • Hierarchical Parallelism: The algorithm exploits both coarse-grained thread-level parallelism and fine-grained data-level parallelism (SIMD).

Experimental Evaluation

The authors evaluated BVC-PLL on 10 diverse real-world datasets, including social networks (DBLP, YouTube), web graphs (Indochina), and communication networks (WikiTalk). The largest graphs contained over 200 million edges.

The results were striking:

  • Sequential Superiority: Even on a single thread, BVC-PLL is over 2x faster than the original sequential PLL. This is rare in parallel computing, where the overhead of making an algorithm "parallel-ready" usually makes it slower on a single thread.
  • Strong Scalability: On a 20-core machine, BVC-PLL achieved up to a 33x speedup over the original sequential PLL and a ~15x speedup over its own 1-thread version.
  • Weighted Graphs: When extended to weighted graphs, BVC-PLL outperformed the previous state-of-the-art parallel algorithm (ParaPLL) by over an order of magnitude.

Key Insights: Why the Marriage Works

The success of BVC-PLL stems from a "happy marriage" between the VC model and PLL's pruning logic. By batching landmarks, the algorithm improves data locality, allowing active labels to fit within the CPU's Last Level Cache (LLC). Furthermore, messages are grouped, leading to a 5x to 18x reduction in total edge accesses. The vertex-centric approach also exploits "intra-group" savings: vertices arriving in the same "wave" (at the same distance) don't need to be checked against each other.

Conclusion

BVC-PLL demonstrates that the Vertex-Centric model can actually enhance the efficiency of complex graph algorithms like PLL. By combining hierarchical parallelism with low-level hardware optimizations, the authors have provided a highly scalable solution for one of the most challenging problems in graph processing. Future work includes exploring "out-of-core" implementations for graphs too large for RAM.

Summary updated

Abstract

In this paper, we study how the Pruned Landmark Labeling (PPL) algorithm can be parallelized in a scalable fashion, producing the same results as the sequential algorithm. More specifically, we parallelize using a Vertex-Centric (VC) computational model on a modern SIMD powered multicore architecture. We design a new VC-PLL algorithm that resolves the apparent mismatch between the inherent sequential dependence of the PLL algorithm and the Vertex- Centric (VC) computing model. Furthermore, we introduce a novel batch execution model for VC computation and the BVC-PLL algorithm to reduce the computational inefficiency in VC-PLL. Quite surprisingly, the theoretical analysis reveals that under a reasonable assumption, BVC-PLL has lower computational and memory access costs than PLL and indicates it may run faster than PLL as a sequential algorithm. We also demonstrate how BVC-PLL algorithm can be extended to handle directed graphs and weighted graphs and how it can utilize the hierarchical parallelism on a modern parallel computing architecture. Extensive experiments on real-world graphs not only show the sequential BVC-PLL can run more than two times faster than the original PLL, but also demonstrates its parallel efficiency and scalability.
BibTeX
@misc{jin2019pruned,
  author = {Ruoming Jin and Zhen Peng and Wendell Wu and Feodor F. Dragan and Gagan Agrawal and Bin Ren},
  title = {{Pruned Landmark Labeling Meets Vertex Centric Computation: A Surprisingly Happy Marriage!}},
  year = {2019},
  eprint = {1906.12018},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1906.12018},
}
Figure