I/O Efficient Label-Constrained Reachability Queries in Large Graphs

Summary: Addresses external-memory label-constrained reachability, where prior in-memory methods incur prohibitive I/O on massive graphs. Two semantics-preserving graph reductions yield an adaptive LCR-Index, enabling sequential-scan queries and scaling to billion-edge graphs. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h3bded95c26f0ab11
Venue: VLDB
Year: 2024
Pagerank: 5.1257999e-05
Overall Rank: 9,805 | 34.08%
DOI: 10.14778/3675034.3675049

Incoming Non-self Citations Over Time

Authors

1. Long Yuan (Nanjing University)
2. Xia Li (University of New South Wales)
3. Zi Chen (Nanjing University)
4. Xuemin Lin (Shanghai Jiao Tong University)
5. Xiang Zhao (National University of Defense Technology)
6. Wenjie Zhang (University of New South Wales)

BibTeX Citation

@article{yuan_vldb24,
        title = {{I/O Efficient Label-Constrained Reachability Queries in Large Graphs}},
        author = {Yuan, Long and Li, Xia and Chen, Zi and Lin, Xuemin and Zhao, Xiang and Zhang, Wenjie},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {10},
        pages = {2590--2602},
        doi = {10.14778/3675034.3675049},
        url = {https://doi.org/10.14778/3675034.3675049},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,895	Simpler is More: Efficient Top-K Nearest Neighbors Search on Large Road Networks	2024	VLDB	5.2559789e-05
10,571	Gem: Scalable Monotonic Graph Processing Beyond Billion-Scale on a Single Machine	2026	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
100	Truss Decomposition in Massive Networks	2012	VLDB	0.00033977856
239	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.000235107
274	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022490994
540	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00016726545
600	Massive Graph Triangulation	2013	SIGMOD	0.00015740352
645	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00015213733
1,329	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD	0.00011000029
1,563	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010224369
2,101	DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine	2016	SIGMOD	9.0476814e-05
2,257	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.7434588e-05
2,534	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	8.3335732e-05
2,563	SCARAB: Scaling Reachability Computation on Large Graphs	2012	SIGMOD	8.2934229e-05
2,734	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	8.0789676e-05
3,348	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	7.3926236e-05
4,049	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.8302372e-05
6,177	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	5.8598586e-05
6,211	I/O Efficient ECC Graph Decomposition via Graph Reduction	2016	VLDB	5.8487355e-05
6,765	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB	5.6872079e-05
6,961	Towards Maximum Independent Sets on Massive Graphs	2015	VLDB	5.6332537e-05
7,377	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	5.5395908e-05
9,936	Divide & Conquer: I/O Efficient Depth-First Search	2015	SIGMOD	5.1074935e-05
12,530	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD	4.9793485e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,348	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB
2	7,840	DAG Reduction: Fast Answering Reachability Queries	2017	SIGMOD
3	3,934	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD
4	4,049	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB
5	1,849	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	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	774	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD
9	6,765	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB
10	6,177	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB