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.2399221e-05
Overall Rank: 5,987 | 58.40%
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,943	Comparing Hierarchical Data in External Memory	1999	VLDB	5.8123762e-05
8,240	Machine Models and Lower Bounds for Query Processing	2007	PODS	4.5471173e-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.0032118946
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
356	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00026091196
923	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015254021
1,389	The Input/Output Complexity Of Transitive Closure	1990	SIGMOD	0.00012247602
1,485	On the Analysis of Indexing Schemes	1997	PODS	0.00011698762
1,499	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643887
2,018	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.7852268e-05
2,119	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5036401e-05
2,139	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4618572e-05
4,736	Memory-Adaptive External Sorting	1993	VLDB	5.9537256e-05
4,826	Dynamic Memory Adjustment for External Mergesort	1997	VLDB	5.8892345e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,081	Global Memory Management in Client-Server DBMS Architectures	1992	VLDB	5.7078887e-05
7,457	A Study of Sort Algorithms for Multiprocessor Database Machines	1986	VLDB	4.7202404e-05
5,320	On Finding Skylines in External Memory	2011	PODS	5.5677544e-05
7,166	Automatic Synthesis of Out-of-Core Algorithms	2013	SIGMOD	4.8077578e-05
3,742	Query Processing in Tertiary Memory Databases	1995	VLDB	6.7950057e-05
4,826	Dynamic Memory Adjustment for External Mergesort	1997	VLDB	5.8892345e-05
52	Database Architecture Optimized for the new Bottleneck: Memory Access	1999	VLDB	0.00066322421
2,582	Database Architectures for New Hardware	2004	VLDB	8.4982366e-05
4,736	Memory-Adaptive External Sorting	1993	VLDB	5.9537256e-05
5,194	Clustering Techniques for Minimizing External Path Length	1996	VLDB	5.6318244e-05