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.8874739e-05
Overall Rank
2,188 | 85.30%
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,943 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 7.8314485e-05
4,488 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 6.5781787e-05
5,000 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 6.3202341e-05
5,703 Hub Labeling for Shortest Path Counting 2020 SIGMOD 6.0303375e-05
5,803 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 5.9893561e-05
6,526 CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression 2023 SIGMOD 5.7559739e-05
6,988 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.6274541e-05
7,302 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 5.5602499e-05
7,747 RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs 2021 VLDB 5.4601389e-05
8,393 Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs 2024 SIGMOD 5.3410533e-05
9,166 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 5.2148514e-05
9,543 FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints 2022 VLDB 5.1614165e-05
10,004 PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks 2024 VLDB 5.0979044e-05
10,255 Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs 2025 SIGMOD 5.050482e-05
10,274 Succinct Graph Representations as Distance Oracles: An Experimental Evaluation 2022 VLDB 5.0485061e-05
10,576 Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks 2026 SIGMOD 4.9793485e-05
10,685 Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC 2026 SIGMOD 4.9793485e-05
11,205 Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks 2025 SIGMOD 4.9793485e-05
11,251 Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs 2025 VLDB 4.9793485e-05
11,449 A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks 2025 VLDB 4.9793485e-05
11,580 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.9793485e-05
11,716 QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks 2023 SIGMOD 4.9793485e-05
11,775 Approximating Probabilistic Group Steiner Trees in Graphs 2023 VLDB 4.9793485e-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