DBScholar

Back to papers

When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks

Summary: H2H-Index: a hierarchical 2-hop labeling that preserves a global vertex hierarchy. Efficient distance queries by visiting a subset of labels; distance-preserved-graph construction with partial-label propagation; experiments on large road networks show an order-of-magnitude speedup. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
5621
Venue
SIGMOD
Year
2018
Pagerank
0.00010216983
Overall Rank
1,613 | 88.94%
DOI
10.1145/3183713.3196913

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{ouyang_sigmod18,
        title = {{When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks}},
        author = {Ouyang, Dian and Qin, Lu and Chang, Lijun and Lin, Xuemin and Zhang, Ying and Zhu, Qing},
        series = {{SIGMOD} '18},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3183713.3196913},
        url = {https://dl.acm.org/doi/10.1145/3183713.3196913},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 34 of 34 citing papers.

Rank Citing Paper Year Venue Pagerank
2,097 Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees 2020 VLDB 9.1725037e-05
2,152 Scaling Distance Labeling on Small-World Networks 2019 SIGMOD 9.0778596e-05
2,871 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 8.0110616e-05
3,612 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 7.2579119e-05
4,403 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 6.7229209e-05
4,786 Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks 2020 SIGMOD 6.5083151e-05
4,807 Diversified Top-k Route Planning in Road Network 2022 VLDB 6.4992836e-05
5,208 Efficient Shortest Path Counting on Large Road Networks 2022 VLDB 6.3165129e-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
5,987 Progressive Top-K Nearest Neighbors Search in Large Road Networks 2020 SIGMOD 6.0183678e-05
6,292 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 5.9251728e-05
6,844 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.7566172e-05
7,226 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB 5.6667372e-05
8,731 Simpler is More: Efficient Top-K Nearest Neighbors Search on Large Road Networks 2024 VLDB 5.3766157e-05
8,911 Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach 2024 SIGMOD 5.3483178e-05
9,229 Continuously Monitoring Alternative Shortest Paths on Road Networks 2020 VLDB 5.3017894e-05
9,364 FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints 2022 VLDB 5.2798829e-05
9,619 Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025 SIGMOD 5.2434488e-05
9,815 PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks 2024 VLDB 5.214913e-05
10,240 Fast Estimation of Pairwise Biharmonic Distance on Graphs 2026 SIGMOD 5.093636e-05
10,366 Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach 2026 SIGMOD 5.093636e-05
10,379 Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks 2026 SIGMOD 5.093636e-05
10,460 High-Throughput k Nearest Neighbors Search in Road Networks 2026 SIGMOD 5.093636e-05
10,788 Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 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
10,860 Continuous Lifelong Conflict-Aware AGV Routing with Kinematic Constraints 2025 VLDB 5.093636e-05
10,918 Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks 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,272 Efficient kNN Search in Public Transportation Networks 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,439 TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks 2023 VLDB 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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