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: 2531
Venue: SIGMOD
Year: 1990
Pagerank: 9.606146e-05
Overall Rank: 1,855 | 87.28%
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
301	Proximity Search in Databases	1998	VLDB	0.00022032878
542	Hexastore: Sextuple Indexing for Semantic Web Data Management	2008	VLDB	0.00016838296
2,957	Graph-Theoretic Methods In Database Theory	1990	PODS	7.9200375e-05
3,491	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD	7.3658999e-05
6,289	External Memory Algorithms	1998	PODS	5.9261616e-05
6,840	Hybrid Transitive Closure Algorithms	1990	VLDB	5.7575344e-05
7,581	Blocking for External Graph Searching (Extended Abstract)	1993	PODS	5.5923369e-05
8,035	On Tree-Based Techniques for Query Evaluation	1992	PODS	5.5028526e-05
13,123	Indexing in a Hypertext Database	1990	VLDB	5.093636e-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,114	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB	0.00012118382
1,330	Efficient Transitive Closure Algorithms	1988	VLDB	0.00011140171

Semantically Similar Papers

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