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.00036215179 |
| 624 | Hexastore: Sextuple Indexing for Semantic Web Data Management | 2008 | VLDB | 0.00018988711 |
| 2,474 | Graph-Theoretic Methods In Database Theory | 1990 | PODS | 8.7135761e-05 |
| 2,675 | A Performance Study Of Transitive Closure Algorithms | 1994 | SIGMOD | 8.3315228e-05 |
| 5,979 | External Memory Algorithms | 1998 | PODS | 5.2450009e-05 |
| 6,504 | Hybrid Transitive Closure Algorithms | 1990 | VLDB | 5.0357556e-05 |
| 7,293 | On Tree-Based Techniques for Query Evaluation | 1992 | PODS | 4.7740089e-05 |
| 7,442 | Blocking for External Graph Searching (Extended Abstract) | 1993 | PODS | 4.7300735e-05 |
| 12,928 | Indexing in a Hypertext Database | 1990 | VLDB | 4.1945683e-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.00016369666 |
| 880 | Efficient Transitive Closure Algorithms | 1988 | VLDB | 0.00015667998 |
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.00016369666 |
| 589 | Massive Graph Triangulation | 2013 | SIGMOD | 0.00019576567 |
| 1,553 | A Memory Efficient Reachability Data Structure Through Bit Vector Compression | 2011 | SIGMOD | 0.00011402871 |
| 246 | Efficient Management of Transitive Relationships in Large Data and Knowledge Bases | 1989 | SIGMOD | 0.00030949575 |
| 1,055 | On The Computation Of The Transitive Closure Of Relational Operators | 1986 | VLDB | 0.00014422575 |
| 7,293 | On Tree-Based Techniques for Query Evaluation | 1992 | PODS | 4.7740089e-05 |
| 2,675 | A Performance Study Of Transitive Closure Algorithms | 1994 | SIGMOD | 8.3315228e-05 |
| 12,041 | I/O Efficient: Computing SCCs in Massive Graphs | 2013 | SIGMOD | 4.1945683e-05 |
| 880 | Efficient Transitive Closure Algorithms | 1988 | VLDB | 0.00015667998 |
| 5,492 | Mixed-Approach Algorithms for Transitive Closure | 1991 | PODS | 5.4771871e-05 |