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.
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.
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