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
h5cf3b69048988921
Venue
SIGMOD
Year
2019
Pagerank
8.8832666e-05
Overall Rank
2,190 | 85.29%
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,944 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 7.8277412e-05
4,491 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 6.5750647e-05
5,004 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 6.3172422e-05
5,705 Hub Labeling for Shortest Path Counting 2020 SIGMOD 6.0274828e-05
5,804 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 5.9865208e-05
6,529 CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression 2023 SIGMOD 5.7532491e-05
6,991 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.6247902e-05
7,305 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 5.5576178e-05
7,753 RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs 2021 VLDB 5.4575542e-05
8,397 Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs 2024 SIGMOD 5.3385249e-05
9,175 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 5.2123828e-05
9,553 FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints 2022 VLDB 5.1589731e-05
10,009 PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks 2024 VLDB 5.0954911e-05
10,261 Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs 2025 SIGMOD 5.0480912e-05
10,280 Succinct Graph Representations as Distance Oracles: An Experimental Evaluation 2022 VLDB 5.0461162e-05
10,587 Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks 2026 SIGMOD 4.9769913e-05
10,696 Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC 2026 SIGMOD 4.9769913e-05
11,214 Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks 2025 SIGMOD 4.9769913e-05
11,259 Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs 2025 VLDB 4.9769913e-05
11,455 A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks 2025 VLDB 4.9769913e-05
11,586 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.9769913e-05
11,722 QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks 2023 SIGMOD 4.9769913e-05
11,781 Approximating Probabilistic Group Steiner Trees in Graphs 2023 VLDB 4.9769913e-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