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: 6397
Venue: SIGMOD
Year: 2022
Pagerank: 5.6858492e-05
Overall Rank: 7,158 | 50.90%
DOI: 10.1145/3514221.3517883

Incoming Non-self Citations Over Time

Authors

1. Muhammad Farhan (Australian National University)
2. Qing Wang (Australian National University)
3. Henning Koehler (Massey University)

BibTeX Citation

@inproceedings{farhan_sigmod22,
        title = {{BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale}},
        author = {Farhan, Muhammad and Wang, Qing and Koehler, Henning},
        series = {{SIGMOD} '22},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3514221.3517883},
        url = {https://dl.acm.org/doi/10.1145/3514221.3517883},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,504	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	5.4132367e-05
9,553	Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs	2025	VLDB	5.2528121e-05
10,748	Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs	2025	SIGMOD	5.093636e-05
10,845	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	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

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
195	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025813775
370	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019937972
1,232	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00011566372
1,309	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.00011210911
1,622	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010201102
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,200	Efficient Network-Aware Search in Collaborative Tagging Sites	2008	VLDB	8.9664473e-05
2,209	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.9437338e-05
5,784	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	6.0896788e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,474	Querying Big Graphs within Bounded Resources	2014	SIGMOD
2	6,603	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB
3	1,553	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB
4	5,784	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD
5	11,248	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB
6	10,845	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB
7	1,796	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD
8	1,232	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD
9	7,322	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB
10	9,619	Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks	2025	SIGMOD