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

Summary: DLCR maintains 2-hop LCR indexes under edge insertions/deletions, including batched updates, on dynamic edge-labeled graphs. Surprisingly, a query-friendly rather than update-friendly layout delivers strong update performance while retaining equivalent asymptotic complexity. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12856
Venue: VLDB
Year: 2022
Pagerank: 5.644647e-05
Overall Rank: 7,322 | 49.77%
DOI: 10.14778/3529337.3529348

Incoming Non-self Citations Over Time

Authors

1. Xin Chen (Chinese University of Hong Kong)
2. You Peng (Chinese University of Hong Kong)
3. Sibo Wang (Chinese University of Hong Kong)
4. Jeffrey Xu Yu (Chinese University of Hong Kong)

BibTeX Citation

@article{chen_vldb22,
        title = {{DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs}},
        author = {Chen, Xin and Peng, You and Wang, Sibo and Yu, Jeffrey Xu},
        journal = {PVLDB},
        series = {{VLDB} '22},
        volume = {15},
        number = {8},
        pages = {1645--1657},
        doi = {10.14778/3529337.3529348},
        url = {https://doi.org/10.14778/3529337.3529348},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,674	Efficient Core Maintenance in Large Bipartite Graphs	2023	SIGMOD	6.1255689e-05
8,046	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	5.5007031e-05
9,625	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	5.2434488e-05
10,361	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	5.093636e-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
195	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025813775
746	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00014402233
1,598	Efficient Route Planning on Public Transportation Networks: A Labelling Approach	2015	SIGMOD	0.00010242826
1,796	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	9.7380494e-05
2,490	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	8.5090456e-05
2,555	Effective Indexing for Approximate Constrained Shortest Path Queries on Large Road Networks	2017	VLDB	8.4184379e-05
2,700	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	8.2411888e-05
2,798	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	8.1129891e-05
2,826	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	8.0865974e-05
3,473	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	7.3864987e-05
6,603	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	5.824568e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,979	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB
2	7,158	BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale	2022	SIGMOD
3	9,132	HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs	2023	SIGMOD
4	4,289	Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs	2016	SIGMOD
5	746	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD
6	2,700	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD
7	2,490	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD
8	1,796	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD
9	6,603	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB
10	9,625	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB