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: h1923381e25b3d1b0
Venue: VLDB
Year: 2022
Pagerank: 5.6872079e-05
Overall Rank: 6,765 | 54.52%
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 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,629	Efficient Core Maintenance in Large Bipartite Graphs	2023	SIGMOD	6.0592611e-05
8,211	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	5.3772821e-05
9,805	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	5.1257999e-05
10,561	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.9793485e-05
10,782	Testing Graph Databases via Transformations Between Fixed-Length and Variable-Length Queries	2026	VLDB	4.9793485e-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
197	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025584127
774	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00014083518
1,621	Efficient Route Planning on Public Transportation Networks: A Labelling Approach	2015	SIGMOD	0.00010054061
1,849	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	9.5068688e-05
2,534	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	8.3335732e-05
2,602	Effective Indexing for Approximate Constrained Shortest Path Queries on Large Road Networks	2017	VLDB	8.2325477e-05
2,734	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	8.0789676e-05
2,851	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.9419904e-05
2,869	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.9235321e-05
3,523	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	7.2343247e-05
6,177	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	5.8598586e-05

Semantically Similar Papers

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