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.00020838159
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.00022490994
288	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00021969641
355	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020124083
382	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019485934
693	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00014734389
774	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00014083518
783	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00014021799
1,133	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00011898162
1,563	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010224369
1,849	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	9.5068688e-05
1,864	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB	9.4824224e-05
2,563	SCARAB: Scaling Reachability Computation on Large Graphs	2012	SIGMOD	8.2934229e-05
2,604	K-Reach: Who is in Your Small World	2012	VLDB	8.2302549e-05
3,056	The Case for RodentStore, an Adaptive, Declarative Storage System	2009	CIDR	7.6972474e-05
3,348	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	7.3926236e-05
4,049	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.8302372e-05
5,000	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	6.3202341e-05
5,101	Relational Approach for Shortest Path Discovery over Large Graphs	2012	VLDB	6.2732849e-05
5,717	Microblog Entity Linking with Social Temporal Context	2015	SIGMOD	6.0191048e-05
5,748	An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels	2010	SIGMOD	6.0079624e-05
6,334	Cloud-based RDF Data Management	2014	SIGMOD	5.810781e-05
6,939	ROLL: Fast In-Memory Generation of Gigantic Scale-free Networks	2016	SIGMOD	5.6391078e-05
7,724	Minimum Strongly Connected Subgraph Collection in Dynamic Graphs	2024	VLDB	5.4672516e-05
7,840	DAG Reduction: Fast Answering Reachability Queries	2017	SIGMOD	5.442834e-05
7,913	Triangular Stability Maximization by Influence Spread over Social Networks	2023	VLDB	5.4277727e-05
8,042	Adaptive Optimizations of Recursive Queries in Teradata	2012	SIGMOD	5.4014499e-05
8,789	Distributed Set Reachability	2016	SIGMOD	5.2767294e-05
9,043	GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases	2010	SIGMOD	5.2315718e-05
9,303	HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs	2023	SIGMOD	5.1978865e-05
9,407	Continuously Monitoring Alternative Shortest Paths on Road Networks	2020	VLDB	5.1828314e-05
11,709	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	4.9793485e-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.00021927874
453	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00017972038
1,110	New Strategies for Computing the Transitive Closure of a Database Relation	1987	VLDB	0.00011984945
1,140	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB	0.00011853213
1,350	GraphDB: Modeling and Querying Graphs in Databases	1994	VLDB	0.0001094492

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,808	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,027	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD
4	3,499	iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques	2010	VLDB
5	774	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD
6	355	On Graph Query Optimization in Large Networks	2010	VLDB
7	1,849	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