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
5689
Venue
SIGMOD
Year
2019
Pagerank
8.3975113e-05
Overall Rank
2,639 | 81.65%
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,342 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 7.197276e-05
5,035 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 5.7470184e-05
5,540 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 5.4498271e-05
5,932 Hub Labeling for Shortest Path Counting 2020 SIGMOD 5.2670741e-05
6,494 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.0417258e-05
6,985 CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression 2023 SIGMOD 4.8729387e-05
7,441 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 4.7302202e-05
7,804 RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs 2021 VLDB 4.6466513e-05
8,256 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 4.5490743e-05
8,967 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 4.4190656e-05
9,089 Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs 2024 SIGMOD 4.39898e-05
9,205 FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints 2022 VLDB 4.3736393e-05
9,680 PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks 2024 VLDB 4.3047774e-05
10,088 Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks 2026 SIGMOD 4.1945683e-05
10,209 Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC 2026 SIGMOD 4.1945683e-05
10,467 Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs 2025 SIGMOD 4.1945683e-05
10,516 Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks 2025 SIGMOD 4.1945683e-05
10,584 Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs 2025 VLDB 4.1945683e-05
10,874 A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks 2025 VLDB 4.1945683e-05
11,038 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.1945683e-05
11,199 QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks 2023 SIGMOD 4.1945683e-05
11,264 Approximating Probabilistic Group Steiner Trees in Graphs 2023 VLDB 4.1945683e-05
11,376 Succinct Graph Representations as Distance Oracles: An Experimental Evaluation 2022 VLDB 4.1945683e-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.00030040036
376 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00025097452
1,170 Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation 2012 VLDB 0.00013511856
1,654 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.000109978
1,823 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010413508
1,838 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB 0.00010349881
2,201 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 9.3048105e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
8,256 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 4.5490743e-05
6,138 Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks 2021 SIGMOD 5.1915368e-05
6,795 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 4.9242446e-05
10,584 Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs 2025 VLDB 4.1945683e-05
1,838 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB 0.00010349881
1,823 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010413508
5,035 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 5.7470184e-05
11,038 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.1945683e-05
8,967 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 4.4190656e-05
260 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00030040036