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.00020800828
Overall Rank: 331 | 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
269	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022625826
288	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022009138
356	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020086045
376	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019655871
694	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00014681018
779	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00014049427
786	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00013979657
1,136	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00011857445
1,564	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010186448
1,859	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	9.4722343e-05
1,873	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB	9.4472588e-05
2,568	SCARAB: Scaling Reachability Computation on Large Graphs	2012	SIGMOD	8.2649684e-05
2,617	K-Reach: Who is in Your Small World	2012	VLDB	8.2001569e-05
3,068	The Case for RodentStore, an Adaptive, Declarative Storage System	2009	CIDR	7.6696594e-05
3,357	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	7.3652047e-05
4,076	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.8048601e-05
5,026	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	6.2965202e-05
5,115	Relational Approach for Shortest Path Discovery over Large Graphs	2012	VLDB	6.2559695e-05
5,732	Microblog Entity Linking with Social Temporal Context	2015	SIGMOD	5.9963673e-05
5,748	An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels	2010	SIGMOD	5.9914851e-05
6,349	Cloud-based RDF Data Management	2014	SIGMOD	5.788832e-05
6,960	ROLL: Fast In-Memory Generation of Gigantic Scale-free Networks	2016	SIGMOD	5.6183097e-05
7,743	Minimum Strongly Connected Subgraph Collection in Dynamic Graphs	2024	VLDB	5.4465939e-05
7,861	DAG Reduction: Fast Answering Reachability Queries	2017	SIGMOD	5.4225547e-05
7,933	Triangular Stability Maximization by Influence Spread over Social Networks	2023	VLDB	5.4072642e-05
8,067	Adaptive Optimizations of Recursive Queries in Teradata	2012	SIGMOD	5.3810658e-05
8,816	Distributed Set Reachability	2016	SIGMOD	5.2567916e-05
9,071	GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases	2010	SIGMOD	5.2118226e-05
9,324	HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs	2023	SIGMOD	5.1815803e-05
9,442	Continuously Monitoring Alternative Shortest Paths on Road Networks	2020	VLDB	5.1632484e-05
11,761	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	4.9605343e-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
293	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00021884281
456	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00017946233
1,112	New Strategies for Computing the Transitive Closure of a Database Relation	1987	VLDB	0.00011945358
1,142	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB	0.00011812263
1,352	GraphDB: Modeling and Querying Graphs in Databases	1994	VLDB	0.00010913807

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,832	Nanosecond Indexing of Graph Data With Hash Maps and VLists	2019	SIGMOD
2	1,577	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB
3	6,043	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD
4	779	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD
5	3,504	iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques	2010	VLDB
6	356	On Graph Query Optimization in Large Networks	2010	VLDB
7	1,859	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	694	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB