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)

Paper ID: hba5e59c662c9ae08
Venue: SIGMOD
Year: 1990
Pagerank: 9.3991536e-05
Overall Rank: 1,904 | 87.21%
DOI: 10.1145/93597.93620

Incoming Non-self Citations Over Time

Authors

1. Jeffrey D. Ullman (Stanford University)
2. Mihalis Yannakakis (AT&T)

BibTeX Citation

@inproceedings{ullman_sigmod90,
        title = {{THE INPUT/OUTPUT COMPLEXITY OF TRANSITIVE CLOSURE}},
        author = {Ullman, Jeffrey D. and Yannakakis, Mihalis},
        series = {{SIGMOD} '90},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/93597.93620},
        url = {https://dl.acm.org/doi/10.1145/93597.93620},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
303	Proximity Search in Databases	1998	VLDB	0.0002164278
557	Hexastore: Sextuple Indexing for Semantic Web Data Management	2008	VLDB	0.00016497067
3,020	Graph-Theoretic Methods In Database Theory	1990	PODS	7.7448163e-05
3,555	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD	7.2086693e-05
6,413	External Memory Algorithms	1998	PODS	5.7931958e-05
6,981	Hybrid Transitive Closure Algorithms	1990	VLDB	5.6287975e-05
7,725	Blocking for External Graph Searching (Extended Abstract)	1993	PODS	5.4669109e-05
8,195	On Tree-Based Techniques for Query Evaluation	1992	PODS	5.3798301e-05
13,413	Indexing in a Hypertext Database	1990	VLDB	4.9793485e-05

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
1,140	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB	0.00011853213
1,363	Efficient Transitive Closure Algorithms	1988	VLDB	0.00010914322

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,140	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB
2	600	Massive Graph Triangulation	2013	SIGMOD
3	1,329	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD
4	294	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD
5	1,287	On the Computation of the Transitive Closure of Relational Operators	1986	VLDB
6	8,195	On Tree-Based Techniques for Query Evaluation	1992	PODS
7	3,555	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD
8	12,530	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD
9	1,363	Efficient Transitive Closure Algorithms	1988	VLDB
10	6,098	Mixed-Approach Algorithms for Transitive Closure	1991	PODS