Reachability Querying: An Independent Permutation Labeling Approach

Summary: Independent-permutation randomized labeling for reachability queries. Claims to be the first approach using independent permutations, achieving linear-time construction and index size with fast querying that avoids run-time DFS; validated on 19 real and synthetic datasets showing efficiency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10779
Venue: VLDB
Year: 2014
Pagerank: 6.1452192e-05
Overall Rank: 4,478 | 68.88%
DOI: -

Incoming Non-self Citations Over Time

Authors

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
3,221	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	7.3541078e-05
3,984	All-in-One: Graph Processing in RDBMSs Revisited	2017	SIGMOD	6.5587512e-05
5,548	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	5.4445937e-05
6,660	On Querying Historical Connectivity in Temporal Graphs	2024	SIGMOD	4.9672425e-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
9,485	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3300131e-05
10,085	GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries	2026	SIGMOD	4.1905499e-05
10,988	Constant-time Connectivity Querying in Dynamic Graphs	2024	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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
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,551	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD	0.00011395294
1,879	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010227906
3,130	SCARAB: Scaling Reachability Computation on Large Graphs	2012	SIGMOD	7.5054361e-05
3,676	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	6.8500097e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,762	K-Reach: Who is in Your Small World	2012	VLDB	8.1614818e-05
1,843	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010340277
5,548	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	5.4445937e-05
7,430	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB	4.7275494e-05
2,958	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	7.8126329e-05
6,796	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9195203e-05
3,676	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	6.8500097e-05
1,776	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.0001058029
784	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016648392
9,485	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3300131e-05