Database Paper Browser

Back to papers

Fast and Practical Indexing and Querying of Very Large Graphs

Summary: GRIPP: Graph indexing by pre/postorder numbering for fast reachability in large graphs. Linear time and space; sub-5 ms reachability on 5M-node graphs; RDBMS stored procedure, evaluated vs prior schemes on real and synthetic graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
3905
Venue
SIGMOD
Year
2007
Pagerank
0.00027081079
Overall Rank
334 | 97.68%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank Citing Paper Year Venue Pagerank
279 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00029113513
376 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00025097452
461 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00022499343
506 On Graph Query Optimization in Large Networks 2010 VLDB 0.00021475362
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
919 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00015343179
951 Comparing Stars: On Approximating Graph Edit Distance 2009 VLDB 0.00015106325
1,777 Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014 SIGMOD 0.00010589591
1,880 TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph 2013 SIGMOD 0.00010226347
2,117 Efficient SimRank-based Similarity Join Over Large Graphs 2013 VLDB 9.5155578e-05
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,280 The Case for RodentStore, an Adaptive, Declarative Storage System 2009 CIDR 7.2828962e-05
3,671 Simple, Fast, and Scalable Reachability Oracle 2013 VLDB 6.8560247e-05
4,478 Reachability Querying: An Independent Permutation Labeling Approach 2014 VLDB 6.1506256e-05
5,215 Relational Approach for Shortest Path Discovery over Large Graphs 2012 VLDB 5.6228603e-05
5,479 Microblog Entity Linking with Social Temporal Context 2015 SIGMOD 5.4850984e-05
5,540 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 5.4498271e-05
5,802 An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels 2010 SIGMOD 5.3209459e-05
6,226 Cloud-based RDF Data Management 2014 SIGMOD 5.1476331e-05
6,974 ROLL: Fast In-Memory Generation of Gigantic Scale-free Networks 2016 SIGMOD 4.8780906e-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
7,798 Triangular Stability Maximization by Influence Spread over Social Networks 2023 VLDB 4.6482149e-05
7,863 Adaptive Optimizations of Recursive Queries in Teradata 2012 SIGMOD 4.6328993e-05
8,669 Distributed Set Reachability 2016 SIGMOD 4.4718257e-05
8,726 GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases 2010 SIGMOD 4.4593116e-05
9,042 HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs 2023 SIGMOD 4.4039656e-05
9,078 Continuously Monitoring Alternative Shortest Paths on Road Networks 2020 VLDB 4.400728e-05
11,191 Parallel Strong Connectivity Based on Faster Reachability 2023 SIGMOD 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 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
425 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00023598882
786 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016660109
815 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.00016369666
1,327 GraphDB: Modeling and Querying Graphs in Databases 1994 VLDB 0.00012569127
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
651 Efficient Subgraph Matching on Billion Node Graphs 2012 VLDB 0.00018648572
1,823 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010413508
6,080 Answering Top-k Representative Queries on Graph Databases 2014 SIGMOD 5.2214553e-05
3,720 iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques 2010 VLDB 6.8192237e-05
788 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD 0.00016650034
506 On Graph Query Optimization in Large Networks 2010 VLDB 0.00021475362
1,777 Reachability Queries on Large Dynamic Graphs: A Total Order Approach 2014 SIGMOD 0.00010589591
203 Graph Indexing: A Frequent Structure-based Approach 2004 SIGMOD 0.00034889335
4,072 Performance and Scalability of Indexed Subgraph Query Processing Methods 2015 VLDB 6.4727847e-05
733 GRAIL: Scalable Reachability Index for Large Graphs 2010 VLDB 0.00017460741