DBScholar

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
5751
Venue
SIGMOD
Year
2019
Pagerank
9.0778596e-05
Overall Rank
2,152 | 85.24%
DOI
10.1145/3299869.3319877

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{li_sigmod19,
        title = {{Scaling Distance Labeling on Small-World Networks}},
        author = {Li, Wentao and Qiao, Miao and Qin, Lu and Zhang, Ying and Chang, Lijun and Lin, Xuemin},
        series = {{SIGMOD} '19},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3299869.3319877},
        url = {https://dl.acm.org/doi/10.1145/3299869.3319877},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 23 of 23 citing papers.

Rank Citing Paper Year Venue Pagerank
2,871 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 8.0110616e-05
4,403 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 6.7229209e-05
5,044 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 6.3883109e-05
5,571 Hub Labeling for Shortest Path Counting 2020 SIGMOD 6.1686653e-05
5,678 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 6.1246854e-05
6,408 CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression 2023 SIGMOD 5.8842681e-05
6,844 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.7566172e-05
7,158 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 5.6858492e-05
7,624 RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs 2021 VLDB 5.5805027e-05
9,003 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 5.3345443e-05
9,118 Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs 2024 SIGMOD 5.3201316e-05
9,364 FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints 2022 VLDB 5.2798829e-05
9,815 PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks 2024 VLDB 5.214913e-05
10,379 Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks 2026 SIGMOD 5.093636e-05
10,498 Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC 2026 SIGMOD 5.093636e-05
10,748 Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs 2025 SIGMOD 5.093636e-05
10,789 Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks 2025 SIGMOD 5.093636e-05
10,845 Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs 2025 VLDB 5.093636e-05
11,097 A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks 2025 VLDB 5.093636e-05
11,248 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 5.093636e-05
11,401 QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks 2023 SIGMOD 5.093636e-05
11,463 Approximating Probabilistic Group Steiner Trees in Graphs 2023 VLDB 5.093636e-05
11,574 Succinct Graph Representations as Distance Oracles: An Experimental Evaluation 2022 VLDB 5.093636e-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.

Previous Page 1 / 1 Next

Semantically Similar Papers