BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale

Summary: BatchHL is a batch-dynamic framework for distance queries on evolving graphs, pairing a compact offline distance labelling with online search. It updates labellings under batch changes, with correctness, minimality, and complexity guarantees, plus validation on 14 real networks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6335
Venue: SIGMOD
Year: 2022
Pagerank: 4.7302202e-05
Overall Rank: 7,441 | 48.24%
DOI: 10.1145/3514221.3517883

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,484	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	4.3341665e-05
10,467	Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs	2025	SIGMOD	4.1945683e-05
10,584	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB	4.1945683e-05
10,865	Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs	2025	VLDB	4.1945683e-05
10,874	A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks	2025	VLDB	4.1945683e-05

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.

Rank	Cited Paper	Year	Venue	Pagerank
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030040036
376	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00025097452
1,378	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00012294512
1,654	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.000109978
1,838	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010349881
2,002	Efficient Network Aware Search in Collaborative Tagging Sites	2008	VLDB	9.818583e-05
2,547	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	8.5683079e-05
2,639	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	8.3975113e-05
2,826	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.056119e-05
6,138	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	5.1915368e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,211	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.3563454e-05
6,795	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9242446e-05
1,823	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010413508
6,138	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	5.1915368e-05
11,038	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB	4.1945683e-05
10,584	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB	4.1945683e-05
1,777	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.00010589591
1,378	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00012294512
7,428	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB	4.7320892e-05
9,470	Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks	2025	SIGMOD	4.3341665e-05