Abstract
Point-to-Point Shortest Distance (PPSD) query is a crucial primitive in graph database applications. Hub labeling algorithms compute a labeling that converts a PPSD query into a list intersection problem over a pre-computed indexing, enabling swift query response. However, constructing hub labeling is computationally challenging. Even state-of-the-art parallel algorithms based on Pruned Landmark Labeling (PLL) are plagued by large label size, violation of network hierarchy, poor scalability, and inability to process large graphs. In this paper, we develop novel parallel shared-memory and distributed-memory algorithms for constructing the Canonical Hub Labeling (CHL) that is minimal in size for a given network hierarchy. Our key contribution, the PLaNT algorithm, scales well beyond the limits of current practice by completely avoiding inter-node communication. Compared to sequential PLL, we empirically demonstrate up to 47.4x speedup on a 72-thread shared-memory platform and successful processing of massive graphs whose labels exceed 100GB.
Introduction
Finding the shortest path between two points in a massive graph—such as a social network or a continental road map—is a fundamental task. While classic algorithms like Dijkstra’s work well for single queries, they are too slow for applications requiring millions of "Point-to-Point Shortest Distance" (PPSD) queries per second. Hub Labeling (HL) addresses this by pre-computing a small set of "hubs" for every vertex. A query then becomes a simple list intersection: finding the common hub between two nodes that minimizes the total distance.
The gold standard for this is Pruned Landmark Labeling (PLL). However, PLL is inherently sequential, building shortest-path trees one by one and using labels from previous trees to "prune" (skip) work in the current one. This dependency makes it difficult to parallelize without sacrificing label minimality or incurring massive communication overhead. Furthermore, the resulting labels often exceed the memory capacity of a single machine.
The PLaNT Algorithm
The core contribution of this work is PLaNT (Prune Labels and (do) Not (Prune) Trees). Instead of pruning a tree based on information from other trees—the source of the sequential dependency—PLaNT tracks the "most important ancestor" within its own tree. This allows it to determine if a label is redundant using only local information.
Because PLaNT does not need to check other nodes' labels during its primary phase, it is communication-avoiding and can run on any number of cores or nodes with near-linear scaling. The researchers also introduced a two-step framework called LCC (Label Construction and Cleaning) and a hybrid approach that switches to a distributed cleaning algorithm (DGLL) once a specific heuristic threshold is met. This collaborative memory approach allows the system's total capacity to scale linearly with the number of nodes in a cluster.
Experimental Results
The authors evaluated PLaNT on 12 diverse real-world datasets, including road networks (e.g., Full USA) and scale-free networks (e.g., LiveJournal). The LiveJournal graph served as a stress test, with resulting hub labels exceeding 100GB.
Key findings include:
- Speedup: On a 72-thread shared-memory machine, PLaNT achieved a 47.4x speedup over sequential PLL.
- Distributed Scaling: On a 64-node cluster, it achieved an average 42x speedup over single-node execution.
- Massive Scale: The system processed the LiveJournal graph in less than 40 minutes. Previous state-of-the-art distributed algorithms (like paraPLL) failed to finish or ran out of memory on graphs of this size.
- Query Efficiency: The resulting labels are "Canonical," meaning they are the minimal possible set for a given vertex ranking, ensuring lightning-fast query response times.
Conclusion
PLaNT represents a significant leap in making hub labeling truly scalable across distributed clusters. By breaking the sequential dependency of traditional pruning methods, it enables the processing of graphs an order of magnitude larger than previously possible. Future work may involve optimizing the hybrid model's switching heuristics and utilizing advanced networking features like Remote Direct Memory Access (RDMA) to further enhance the cleaning phase.
Summary updated