DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs

Summary: DLCR extends 2-hop LCR indexing to dynamic edge-labeled graphs with efficient, correct updates. A query-friendly but update-unfriendly index yields the same time complexity as update-friendly schemes, with batched updates. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12668
Venue: VLDB
Year: 2022
Pagerank: 4.7320892e-05
Overall Rank: 7,428 | 48.33%
DOI: 10.14778/3529337.3529348

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,183	Efficient Core Maintenance in Large Bipartite Graphs	2023	SIGMOD	5.1667703e-05
8,170	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	4.5697385e-05
9,483	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3341665e-05
10,070	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 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
788	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016650034
1,555	Efficient Route Planning on Public Transportation Networks: A Labelling Approach	2015	SIGMOD	0.00011395261
1,777	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.00010589591
2,188	Effective Indexing for Approximate Constrained Shortest Path Queries on Large Road Networks	2017	VLDB	9.3372315e-05
2,957	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	7.8198686e-05
3,213	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	7.3669794e-05
3,321	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.223972e-05
3,394	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.1480446e-05
4,191	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	6.3735885e-05
6,795	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9242446e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,478	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.1506256e-05
7,441	BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale	2022	SIGMOD	4.7302202e-05
9,042	HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs	2023	SIGMOD	4.4039656e-05
4,745	Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs	2016	SIGMOD	5.9573154e-05
788	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016650034
3,213	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	7.3669794e-05
2,957	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	7.8198686e-05
1,777	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.00010589591
6,795	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9242446e-05
9,483	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3341665e-05