The input/output complexity of sorting and related problems

By Alok Aggarwal, Jeffrey Scott Vitter. 1988

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022, methodology): “We draw the most direct connection to the literature of analyzing I/O complexity in this work [1], but concepts of memory hierarchies are fundamental and has appeared in many forms, from the working set model [23], to data locality [90], to the Rooﬂine model of arithmetic intensity [89], to…”
PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees (2017, methodology): “We use the standard Disk Access Model (DAM) [2] and assume that each read/write operation can access a block of size B in one unit cost.”
Non-commercial Research and Educational Use including without Limitation Use in Instruction at Your Institution, Sending It to Specific Colleagues That You Know, and Providing a Copy to Your Institution's Administrator. All Other Uses, Reproduction and Distribution, including without Limitation Comm (2005, unknown): “The indirect couplings are usually taken from the corresponding isotropic spectra of the solute or from the literature, and kept fixed.”
Truss Decomposition in Massive Networks (2012, methodology): “When analyzing I/O complexity of our algorithms, we adopt the I/O model in [2]: M is the main memory size and B is the disk block size, where 1 ≪ B ≤ M/ 2 . reading/ Data is read/written in blocks from/to disk.”
GPUTeraSort: high performance graphics co-processor sorting for large database management (2006, background): “In this model, the average and worst case I/O performance of external memory sorting algorithms is ≈ n D logmn where n is the input size, m is the internal memory size, D is the number of disks and logmn denotes the number of passes when the data partition size in the Phase 1 is ≈ m [3, 30].”
GraphChi: Large-Scale Graph Computation on Just a PC (2012, unknown): “We analyze the I/O efficiency of PSW in the I/O model by Aggarwal and Vitter [1].”
Poisson convergence in the restricted k-partitioning problem (2007, methodology): “Unlike having a linear time complexity in RAM model, integer sorting in external memory has same lower and upper bound as that of general sorting [ 1 ].”
Cache-oblivious B-trees (2000, background): “The distinguishing feature of multilevel memory hierarchies is that memory transfers are done in blocks in order to amortize the cost of a transfer [4].”
X-Stream: edge-centric graph processing using streaming partitions (2013, methodology): “To express X-Stream’s capabilities and limitations in more general terms, we examined using the theoretical I/O model [13] the cost of propagating a message from (any) source vertex to all other (assumed reachable) vertices in a graph G = (V,E), modeling label propagation in the graph.”
External memory algorithms and data structures: dealing with massive data (2001, methodology): “THEOREM 5.1 [AGGARWAL AND VITTER 1988; NODINE AND VITTER 1995].”
Minimizing Communication in Numerical Linear Algebra (2009, methodology): “mized versions of each operation in the sequence. We give examples where this 1Thesequentialcommunication modelusedhereissometimes called thetwo-level I/O model ordisk access machine (DAM) model (see [AV88], [BBF+07], [CR06]). Our model follows that of [HK81] and [ITT04] in that it assumes the block”