The Input/Output Complexity Of Transitive Closure
Summary: Analyzes I/O complexity of transitive closure under Kung–Hong with memory s. Dense: O(n^3/√s) I/O suffices and is tight for standard algorithms; sparse: O(n^2√(e/s)) I/O suffices (acyclic standard) with matching lower bound, while restricted-path variants need Ω(n^3√(e/s)/log^3 n) on cyclic graphs. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 9 of 9 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 186 | Proximity Search in Databases | 1998 | VLDB | 0.0003618341 |
| 625 | Hexastore: Sextuple Indexing for Semantic Web Data Management | 2008 | VLDB | 0.00018963452 |
| 2,473 | Graph-Theoretic Methods In Database Theory | 1990 | PODS | 8.7048914e-05 |
| 2,679 | A Performance Study Of Transitive Closure Algorithms | 1994 | SIGMOD | 8.3223476e-05 |
| 5,987 | External Memory Algorithms | 1998 | PODS | 5.2399221e-05 |
| 6,499 | Hybrid Transitive Closure Algorithms | 1990 | VLDB | 5.0307246e-05 |
| 7,289 | On Tree-Based Techniques for Query Evaluation | 1992 | PODS | 4.7692311e-05 |
| 7,440 | Blocking for External Graph Searching (Extended Abstract) | 1993 | PODS | 4.7255744e-05 |
| 12,938 | Indexing in a Hypertext Database | 1990 | VLDB | 4.1905499e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 2 of 2 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 815 | Direct Algorithms for Computing the Transitive Closure of Database Relations | 1987 | VLDB | 0.0001629507 |
| 885 | Efficient Transitive Closure Algorithms | 1988 | VLDB | 0.00015565543 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 815 | Direct Algorithms for Computing the Transitive Closure of Database Relations | 1987 | VLDB | 0.0001629507 |
| 588 | Massive Graph Triangulation | 2013 | SIGMOD | 0.00019588834 |
| 1,551 | A Memory Efficient Reachability Data Structure Through Bit Vector Compression | 2011 | SIGMOD | 0.00011395294 |
| 255 | Efficient Management of Transitive Relationships in Large Data and Knowledge Bases | 1989 | SIGMOD | 0.00030342925 |
| 1,078 | On The Computation Of The Transitive Closure Of Relational Operators | 1986 | VLDB | 0.00014223265 |
| 7,289 | On Tree-Based Techniques for Query Evaluation | 1992 | PODS | 4.7692311e-05 |
| 2,679 | A Performance Study Of Transitive Closure Algorithms | 1994 | SIGMOD | 8.3223476e-05 |
| 12,049 | I/O Efficient: Computing SCCs in Massive Graphs | 2013 | SIGMOD | 4.1905499e-05 |
| 885 | Efficient Transitive Closure Algorithms | 1988 | VLDB | 0.00015565543 |
| 5,504 | Mixed-Approach Algorithms for Transitive Closure | 1991 | PODS | 5.4716648e-05 |