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.1064323e-05
Overall Rank: 9,846 | 34.01%
DOI: 10.14778/3675034.3675049
PDF: Download (CC BY-NC-ND 4.0)

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,923	Simpler is More: Efficient Top-K Nearest Neighbors Search on Large Road Networks	2024	VLDB	5.2361195e-05
10,645	Gem: Scalable Monotonic Graph Processing Beyond Billion-Scale on a Single Machine	2026	SIGMOD	4.9605343e-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
96	Truss Decomposition in Massive Networks	2012	VLDB	0.00034261728
235	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.00023701614
269	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022625826
536	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00016738841
599	Massive Graph Triangulation	2013	SIGMOD	0.00015700433
643	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00015219469
1,341	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD	0.00010960707
1,564	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010186448
2,101	DUALSIM: Parallel Subgraph Enumeration in a Massive Graph on a Single Machine	2016	SIGMOD	9.0309825e-05
2,272	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD	8.7108429e-05
2,541	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	8.3021057e-05
2,568	SCARAB: Scaling Reachability Computation on Large Graphs	2012	SIGMOD	8.2649684e-05
2,744	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	8.0484475e-05
3,357	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	7.3652047e-05
4,076	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.8048601e-05
6,192	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	5.8377174e-05
6,226	I/O Efficient ECC Graph Decomposition via Graph Reduction	2016	VLDB	5.8266364e-05
6,786	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB	5.6657191e-05
6,983	Towards Maximum Independent Sets on Massive Graphs	2015	VLDB	5.6120829e-05
7,399	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	5.5186598e-05
9,976	Divide & Conquer: I/O Efficient Depth-First Search	2015	SIGMOD	5.0881951e-05
12,579	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD	4.9605343e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,357	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB
2	7,861	DAG Reduction: Fast Answering Reachability Queries	2017	SIGMOD
3	3,933	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD
4	4,076	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB
5	1,859	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD
6	2,541	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD
7	2,744	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD
8	779	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD
9	6,786	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB
10	6,192	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB