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
ha7a69f78c48de518
Venue
SIGMOD
Year
2018
Pagerank
0.00010151896
Overall Rank
1,581 | 89.41%
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 35 of 35 citing papers.

Rank Citing Paper Year Venue Pagerank
2,150 Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees 2020 VLDB 8.9509559e-05
2,201 Scaling Distance Labeling on Small-World Networks 2019 SIGMOD 8.8626226e-05
2,794 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 7.987154e-05
3,676 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 7.0882436e-05
4,214 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 6.7186746e-05
4,631 Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks 2020 SIGMOD 6.4784075e-05
4,931 Diversified Top-k Route Planning in Road Network 2022 VLDB 6.3376097e-05
5,357 Efficient Shortest Path Counting on Large Road Networks 2022 VLDB 6.1514562e-05
5,409 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 6.1320768e-05
5,699 Hub Labeling for Shortest Path Counting 2020 SIGMOD 6.0139119e-05
5,899 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 5.9376618e-05
6,073 Progressive Top-K Nearest Neighbors Search in Large Road Networks 2020 SIGMOD 5.8780393e-05
7,008 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.6061911e-05
7,399 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB 5.5186598e-05
8,655 Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach 2024 SIGMOD 5.2794257e-05
8,695 Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025 SIGMOD 5.2717835e-05
8,923 Simpler is More: Efficient Top-K Nearest Neighbors Search on Large Road Networks 2024 VLDB 5.2361195e-05
9,442 Continuously Monitoring Alternative Shortest Paths on Road Networks 2020 VLDB 5.1632484e-05
9,578 FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints 2022 VLDB 5.1419143e-05
9,679 Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks 2026 SIGMOD 5.1258854e-05
10,044 PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks 2024 VLDB 5.0786422e-05
10,414 Tree+DAG: An Efficient Index for Resistance Distance Computation on Core-Periphery Graphs 2027 SIGMOD 4.9605343e-05
10,532 Fast Estimation of Pairwise Biharmonic Distance on Graphs 2026 SIGMOD 4.9605343e-05
10,638 Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach 2026 SIGMOD 4.9605343e-05
10,719 High-Throughput k Nearest Neighbors Search in Road Networks 2026 SIGMOD 4.9605343e-05
11,271 Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 2025 SIGMOD 4.9605343e-05
11,272 Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks 2025 SIGMOD 4.9605343e-05
11,315 Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs 2025 VLDB 4.9605343e-05
11,327 Continuous Lifelong Conflict-Aware AGV Routing with Kinematic Constraints 2025 VLDB 4.9605343e-05
11,373 Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks 2025 VLDB 4.9605343e-05
11,507 A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks 2025 VLDB 4.9605343e-05
11,634 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.9605343e-05
11,653 Efficient kNN Search in Public Transportation Networks 2024 VLDB 4.9605343e-05
11,768 QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks 2023 SIGMOD 4.9605343e-05
11,802 TASK: An Efficient Framework for Instant Error-tolerant Spatial Keyword Queries on Road Networks 2023 VLDB 4.9605343e-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