External Memory Algorithms

Summary: Survey of external-memory algorithm design under the Parallel Disk Model, emphasizing machine-independent metrics (I/O count, CPU time, disk space) and extensions to caches, hierarchies and tertiary storage. Identifies algorithmic paradigms, presents TPIE programming support and reports empirical speedups for spatial-database algorithms. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1136
Venue: PODS
Year: 1998
Pagerank: 5.9261616e-05
Overall Rank: 6,289 | 56.86%
DOI: 10.1145/275487.275501

Incoming Non-self Citations Over Time

Authors

1. Jeffrey Scott Vitter (Duke University)

BibTeX Citation

@inproceedings{vitter_pods98,
        address = {New York, NY, USA},
        series = {{PODS} '98},
        title = {{External Memory Algorithms}},
        url = {https://dl.acm.org/doi/10.1145/275487.275501},
        doi = {10.1145/275487.275501},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Vitter, Jeffrey Scott},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,061	Comparing Hierarchical Data in External Memory	1999	VLDB	6.3801057e-05
8,488	Machine Models and Lower Bounds for Query Processing	2007	PODS	5.4153038e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
329	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00021068647
728	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014542772
1,512	On the Analysis of Indexing Schemes	1997	PODS	0.00010536001
1,561	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00010361147
1,855	The Input/Output Complexity Of Transitive Closure	1990	SIGMOD	9.606146e-05
1,880	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5562066e-05
1,901	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.5068846e-05
2,135	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.1133971e-05
4,708	Memory-Adaptive External Sorting	1993	VLDB	6.5519325e-05
4,955	Dynamic Memory Adjustment for External Mergesort	1997	VLDB	6.4297637e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,705	A Study of Sort Algorithms for Multiprocessor Database Machines	1986	VLDB
2	5,096	Global Memory Management in Client-Server DBMS Architectures	1992	VLDB
3	5,016	On Finding Skylines in External Memory	2011	PODS
4	7,043	Automatic Synthesis of Out-of-Core Algorithms	2013	SIGMOD
5	3,760	Query Processing in Tertiary Memory Databases	1995	VLDB
6	4,955	Dynamic Memory Adjustment for External Mergesort	1997	VLDB
7	29	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB
8	2,870	Database Architectures for New Hardware	2004	VLDB
9	4,708	Memory-Adaptive External Sorting	1993	VLDB
10	5,888	Clustering Techniques for Minimizing External Path Length	1996	VLDB