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: 10684
Venue: VLDB
Year: 2013
Pagerank: 6.8500097e-05
Overall Rank: 3,676 | 74.46%
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,392	Real-time Constrained Cycle Detection in Large Dynamic Graphs	2018	VLDB	0.00012224015
1,776	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.0001058029
3,221	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	7.3541078e-05
4,478	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.1452192e-05
5,488	Microblog Entity Linking with Social Temporal Context	2015	SIGMOD	5.4798261e-05
6,796	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9195203e-05
7,595	DAG Reduction: Fast Answering Reachability Queries	2017	SIGMOD	4.6980168e-05
7,714	Minimum Strongly Connected Subgraph Collection in Dynamic Graphs	2024	VLDB	4.6651585e-05
9,042	HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs	2023	SIGMOD	4.3997447e-05
9,485	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3300131e-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
255	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00030342925
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030020929
280	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029092277
334	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00027077424
425	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00023592024
727	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00017462279
784	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016648392
1,448	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.00011928845
1,551	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD	0.00011395294
1,843	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010340277
1,879	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010227906
2,762	K-Reach: Who is in Your Small World	2012	VLDB	8.1614818e-05
3,130	SCARAB: Scaling Reachability Computation on Large Graphs	2012	SIGMOD	7.5054361e-05
3,949	Efficient Reachability Query Evaluation in Large Spatiotemporal Contact Datasets	2012	VLDB	6.5929931e-05
5,051	Performance Guarantees for Distributed Reachability Queries	2012	VLDB	5.7267112e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,430	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB	4.7275494e-05
7,240	Toward a Distance Oracle for Billion-Node Graphs	2014	VLDB	4.7869144e-05
8,667	Distributed Set Reachability	2016	SIGMOD	4.467539e-05
1,879	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010227906
6,796	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9195203e-05
1,776	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.0001058029
2,958	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	7.8126329e-05
9,485	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3300131e-05
784	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016648392
4,478	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.1452192e-05