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: 3967
Venue: SIGMOD
Year: 2007
Pagerank: 0.00021275303
Overall Rank: 322 | 97.80%
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.00022786599
294	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022253507
352	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020375193
370	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019937972
679	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00015055389
746	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00014402233
776	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00014110016
1,115	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00012117375
1,533	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010467148
1,796	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	9.7380494e-05
1,812	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB	9.6948178e-05
2,575	K-Reach: Who is in Your Small World	2012	VLDB	8.3982298e-05
3,009	The Case for RodentStore, an Adaptive, Declarative Storage System	2009	CIDR	7.8541296e-05
3,021	SCARAB: Scaling Reachability Computation on Large Graphs	2012	SIGMOD	7.8401031e-05
3,278	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB	7.5712342e-05
3,979	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.9754185e-05
4,977	Relational Approach for Shortest Path Discovery over Large Graphs	2012	VLDB	6.4166233e-05
5,044	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	6.3883109e-05
5,590	Microblog Entity Linking with Social Temporal Context	2015	SIGMOD	6.1557283e-05
5,724	An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels	2010	SIGMOD	6.108728e-05
6,258	Cloud-based RDF Data Management	2014	SIGMOD	5.939696e-05
7,002	ROLL: Fast In-Memory Generation of Gigantic Scale-free Networks	2016	SIGMOD	5.7280021e-05
7,578	Minimum Strongly Connected Subgraph Collection in Dynamic Graphs	2024	VLDB	5.5927377e-05
7,707	DAG Reduction: Fast Answering Reachability Queries	2017	SIGMOD	5.5636745e-05
7,771	Triangular Stability Maximization by Influence Spread over Social Networks	2023	VLDB	5.5470467e-05
7,891	Adaptive Optimizations of Recursive Queries in Teradata	2012	SIGMOD	5.5211516e-05
8,651	Distributed Set Reachability	2016	SIGMOD	5.3916003e-05
8,884	GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases	2010	SIGMOD	5.3514928e-05
9,132	HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs	2023	SIGMOD	5.31719e-05
9,229	Continuously Monitoring Alternative Shortest Paths on Road Networks	2020	VLDB	5.3017894e-05
11,394	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	5.093636e-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
282	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.0002242162
444	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00018350865
1,086	New Strategies for Computing the Transitive Closure of a Database Relation	1987	VLDB	0.00012252192
1,114	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB	0.00012118382
1,359	GraphDB: Modeling and Querying Graphs in Databases	1994	VLDB	0.00011040427

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
2	1,553	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB
3	5,965	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD
4	3,431	iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques	2010	VLDB
5	746	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD
6	352	On Graph Query Optimization in Large Networks	2010	VLDB
7	1,796	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD
8	177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD
9	3,477	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB
10	679	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB