Database Paper Browser

Back to papers

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
10778
Venue
VLDB
Year
2014
Pagerank
6.1506256e-05
Overall Rank
4,478 | 68.85%
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,394 Real-time Constrained Cycle Detection in Large Dynamic Graphs 2018 VLDB 0.0001221552
3,213 Landmark Indexing for Evaluation of Label-Constrained Reachability Queries 2017 SIGMOD 7.3669794e-05
3,988 All-in-One: Graph Processing in RDBMSs Revisited 2017 SIGMOD 6.5589605e-05
5,540 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 5.4498271e-05
6,657 On Querying Historical Connectivity in Temporal Graphs 2024 SIGMOD 4.9720132e-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
9,483 I/O Efficient Label-Constrained Reachability Queries in Large Graphs 2024 VLDB 4.3341665e-05
10,085 GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries 2026 SIGMOD 4.1945683e-05
10,985 Constant-time Connectivity Querying in Dynamic Graphs 2024 SIGMOD 4.1945683e-05
Previous Page 1 / 1 Next

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
246 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.00030949575
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,553 A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011 SIGMOD 0.00011402871
1,880 TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013 SIGMOD 0.00010226347
3,127 SCARAB: Scaling Reachability Computation on Large Graphs 2012 SIGMOD 7.5046522e-05
3,671 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 6.8560247e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,756 K-Reach: Who is in Your Small World 2012 VLDB 8.1682536e-05
1,838 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB 0.00010349881
5,540 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 5.4498271e-05
7,428 DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs 2022 VLDB 4.7320892e-05
2,957 Computing Label-Constraint Reachability in Graph Databases 2010 SIGMOD 7.8198686e-05
6,795 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 4.9242446e-05
3,671 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 6.8560247e-05
1,777 Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014 SIGMOD 0.00010589591
788 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD 0.00016650034
9,483 I/O Efficient Label-Constrained Reachability Queries in Large Graphs 2024 VLDB 4.3341665e-05