Database Paper Browser

Back to papers

Scaling Distance Labeling on Small-World Networks

Summary: Proposes PSL to scale distance labeling on small-world graphs, turning PLL's node-order pruning into propagation shortest-distance dependencies. Gives D-round labeling (D) with near-linear multi-core speedups on billion-scale graphs and smaller indices. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
5690
Venue
SIGMOD
Year
2019
Pagerank
8.3894193e-05
Overall Rank
2,643 | 81.64%
DOI
10.1145/3299869.3319877

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 23 of 23 citing papers.

Rank Citing Paper Year Venue Pagerank
3,346 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 7.1903469e-05
5,035 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 5.7414979e-05
5,548 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 5.4445937e-05
5,933 Hub Labeling for Shortest Path Counting 2020 SIGMOD 5.2620152e-05
6,491 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.0368875e-05
6,983 CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression 2023 SIGMOD 4.8682622e-05
7,439 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 4.7256836e-05
7,806 RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs 2021 VLDB 4.6421951e-05
8,252 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 4.544713e-05
8,973 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 4.4148296e-05
9,086 Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs 2024 SIGMOD 4.3947639e-05
9,207 FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints 2022 VLDB 4.3694476e-05
9,680 PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks 2024 VLDB 4.3006524e-05
10,088 Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks 2026 SIGMOD 4.1905499e-05
10,209 Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC 2026 SIGMOD 4.1905499e-05
10,477 Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs 2025 SIGMOD 4.1905499e-05
10,525 Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks 2025 SIGMOD 4.1905499e-05
10,592 Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs 2025 VLDB 4.1905499e-05
10,878 A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks 2025 VLDB 4.1905499e-05
11,041 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.1905499e-05
11,201 QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks 2023 SIGMOD 4.1905499e-05
11,266 Approximating Probabilistic Group Steiner Trees in Graphs 2023 VLDB 4.1905499e-05
11,378 Succinct Graph Representations as Distance Oracles: An Experimental Evaluation 2022 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
260 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00030020929
377 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00025074538
1,173 Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation 2012 VLDB 0.00013501079
1,653 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.0001098717
1,822 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010404349
1,843 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB 0.00010340277
2,206 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 9.2958349e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
8,252 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 4.544713e-05
6,144 Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks 2021 SIGMOD 5.1865526e-05
6,796 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 4.9195203e-05
10,592 Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs 2025 VLDB 4.1905499e-05
1,843 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB 0.00010340277
1,822 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010404349
5,035 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 5.7414979e-05
11,041 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.1905499e-05
8,973 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 4.4148296e-05
260 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00030020929