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: h32f2868f9b09aab2
Venue: SIGMOD
Year: 2007
Pagerank: 0.00020828552
Overall Rank: 330 | 97.79%
DOI: 10.1145/1247480.1247573

Incoming Non-self Citations Over Time

Authors

1. Silke Trißl (Humboldt University of Berlin)
2. Ulf Leser (Humboldt University of Berlin)

BibTeX Citation

@inproceedings{tril_sigmod07,
        title = {{Fast and Practical Indexing and Querying of Very Large Graphs}},
        author = {Trißl, Silke and Leser, Ulf},
        series = {{SIGMOD} '07},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1247480.1247573},
        url = {https://dl.acm.org/doi/10.1145/1247480.1247573},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
274	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022480767
289	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00021960834
355	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020116134
382	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019477423
693	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00014727433
776	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00014076975
784	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00014015324
1,133	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00011892544
1,563	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010219537
1,850	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	9.502574e-05
1,866	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB	9.4779341e-05
2,563	SCARAB: Scaling Reachability Computation on Large Graphs	2012	SIGMOD	8.2895644e-05
2,606	K-Reach: Who is in Your Small World	2012	VLDB	8.2264537e-05
3,059	The Case for RodentStore, an Adaptive, Declarative Storage System	2009	CIDR	7.6939894e-05
3,348	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	7.3891319e-05
4,050	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.8270039e-05
5,004	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	6.3172422e-05
5,104	Relational Approach for Shortest Path Discovery over Large Graphs	2012	VLDB	6.2703153e-05
5,718	Microblog Entity Linking with Social Temporal Context	2015	SIGMOD	6.0162555e-05
5,749	An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels	2010	SIGMOD	6.0051184e-05
6,337	Cloud-based RDF Data Management	2014	SIGMOD	5.8080313e-05
6,943	ROLL: Fast In-Memory Generation of Gigantic Scale-free Networks	2016	SIGMOD	5.6364384e-05
7,730	Minimum Strongly Connected Subgraph Collection in Dynamic Graphs	2024	VLDB	5.4646635e-05
7,844	DAG Reduction: Fast Answering Reachability Queries	2017	SIGMOD	5.4402574e-05
7,918	Triangular Stability Maximization by Influence Spread over Social Networks	2023	VLDB	5.4252033e-05
8,049	Adaptive Optimizations of Recursive Queries in Teradata	2012	SIGMOD	5.3988942e-05
8,798	Distributed Set Reachability	2016	SIGMOD	5.2742315e-05
9,051	GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases	2010	SIGMOD	5.2290958e-05
9,312	HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs	2023	SIGMOD	5.1954259e-05
9,416	Continuously Monitoring Alternative Shortest Paths on Road Networks	2020	VLDB	5.180378e-05
11,715	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	4.9769913e-05

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
294	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00021917638
453	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00017963727
1,110	New Strategies for Computing the Transitive Closure of a Database Relation	1987	VLDB	0.00011979358
1,140	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB	0.00011847659
1,350	GraphDB: Modeling and Querying Graphs in Databases	1994	VLDB	0.00010939854

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,811	Nanosecond Indexing of Graph Data With Hash Maps and VLists	2019	SIGMOD
2	1,585	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB
3	6,030	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD
4	776	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD
5	3,499	iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques	2010	VLDB
6	355	On Graph Query Optimization in Large Networks	2010	VLDB
7	1,850	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD
8	176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD
9	3,506	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB
10	693	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB