Simple, Fast, and Scalable Reachability Oracle

Summary: Hierarchical-Labeling and Distribution-Labeling for reachability; avoid transitive-closure materialization, scalable. No set-cover; construction an order of magnitude faster, with compact indexes and queries beating TC compression and search. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10683
Venue: VLDB
Year: 2013
Pagerank: 6.8560247e-05
Overall Rank: 3,671 | 74.47%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Ruoming Jin
2. Guan Wang

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,394	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.0001221552
1,777	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.00010589591
3,213	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	7.3669794e-05
4,478	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.1506256e-05
5,479	Microblog Entity Linking with Social Temporal Context	2015	SIGMOD	5.4850984e-05
6,795	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9242446e-05
7,596	DAG Reduction: Fast Answering Reachability Queries	2017	SIGMOD	4.7016964e-05
7,716	Minimum Strongly Connected Subgraph Collection in Dynamic Graphs	2024	VLDB	4.6696364e-05
9,042	HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs	2023	SIGMOD	4.4039656e-05
9,483	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3341665e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
246	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00030949575
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030040036
279	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029113513
334	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00027081079
425	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00023598882
733	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00017460741
788	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016650034
1,450	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.00011925844
1,553	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD	0.00011402871
1,838	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010349881
1,880	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010226347
2,756	K-Reach: Who is in Your Small World	2012	VLDB	8.1682536e-05
3,127	SCARAB: Scaling Reachability Computation on Large Graphs	2012	SIGMOD	7.5046522e-05
3,946	Efficient Reachability Query Evaluation in Large Spatiotemporal Contact Datasets	2012	VLDB	6.5993134e-05
5,054	Performance Guarantees for Distributed Reachability Queries	2012	VLDB	5.7321997e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,428	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB	4.7320892e-05
7,236	Toward a Distance Oracle for Billion-Node Graphs	2014	VLDB	4.7932355e-05
8,669	Distributed Set Reachability	2016	SIGMOD	4.4718257e-05
1,880	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010226347
6,795	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9242446e-05
1,777	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.00010589591
2,957	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	7.8198686e-05
9,483	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3341665e-05
4,478	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.1506256e-05
788	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016650034