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: 1137
Venue: PODS
Year: 1998
Pagerank: 5.2450009e-05
Overall Rank: 5,979 | 58.41%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Jeffrey Scott Vitter

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,941	Comparing Hierarchical Data in External Memory	1999	VLDB	5.8179899e-05
8,241	Machine Models and Lower Bounds for Query Processing	2007	PODS	4.5519176e-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.0032169493
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083378538
354	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00026137988
925	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015264328
1,389	The Input/Output Complexity Of Transitive Closure	1990	SIGMOD	0.00012260807
1,488	On the Analysis of Indexing Schemes	1997	PODS	0.00011699446
1,502	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643406
2,013	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.7928688e-05
2,094	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5547223e-05
2,136	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4721139e-05
4,741	Memory-Adaptive External Sorting	1993	VLDB	5.95905e-05
4,832	Dynamic Memory Adjustment for External Mergesort	1997	VLDB	5.8924168e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,460	A Study of Sort Algorithms for Multiprocessor Database Machines	1986	VLDB	4.7241128e-05
5,085	Global Memory Management in Client-Server DBMS Architectures	1992	VLDB	5.7089113e-05
5,240	On Finding Skylines in External Memory	2011	PODS	5.6104868e-05
7,167	Automatic Synthesis of Out-of-Core Algorithms	2013	SIGMOD	4.8123187e-05
3,740	Query Processing in Tertiary Memory Databases	1995	VLDB	6.8015038e-05
4,832	Dynamic Memory Adjustment for External Mergesort	1997	VLDB	5.8924168e-05
52	Database Architecture Optimized for the new Bottleneck: Memory Access	1999	VLDB	0.00066474881
2,582	Database Architectures for New Hardware	2004	VLDB	8.5007371e-05
4,741	Memory-Adaptive External Sorting	1993	VLDB	5.95905e-05
5,196	Clustering Techniques for Minimizing External Path Length	1996	VLDB	5.6365164e-05