Communications of the ACM
Lower Bounds for External Memory Integer Sorting via Network Coding
Credit: Wikimedia
Sorting extremely large datasets is a frequently occurring task in practice. These datasets are usually much larger than the computer's main memory; thus, external memory sorting algorithms, first introduced by Aggarwal and Vitter, are often used. The complexity of comparison-based external memory sorting has been understood for decades by now; however, the situation remains elusive if we assume the keys to be sorted are integers. In internal memory, one can sort a set of n integer keys of Θ(lg n) bits each in O(n) time using the classic Radix Sort algorithm; however, in external memory, there are no faster integer sorting algorithms known than the simple comparison-based ones. Whether such algorithms exist has remained a central open problem in external memory algorithms for more than three decades.
In this paper, we present a tight conditional lower bound on the complexity of external memory sorting of integers. Our lower bound is based on a famous conjecture in network coding by Li and Li, who conjectured that network coding cannot help anything beyond the standard multicommodity flow rate in undirected graphs.
The only previous work connecting the Li and Li conjecture to lower bounds for algorithms is due to Adler et al. Adler et al. indeed obtain relatively simple lower bounds for oblivious algorithms (the memory access pattern is fixed and independent of the input data). Unfortunately, obliviousness is a strong limitation, especially for integer sorting: we show that the Li and Li conjecture implies an Ω(n lg n) lower bound for internal memory oblivious sorting when the keys are Θ(lg n) bits. This is in sharp contrast to the classic (nonoblivious) Radix Sort algorithm. Indeed, going beyond obliviousness is highly nontrivial; we need to introduce several new methods and involved techniques, which are of their own interest, to obtain our tight lower bound for external memory integer sorting.
1. Introduction
Sorting is one of the most basic algorithmic primitives and has attracted lots of attention from the beginning of the computing era. Many classical algorithms have been designed for this problem such as Merge Sort, Bubble Sort, Insertion Sort, etc. As sorting extremely large data has become essential for many applications, there has been a strong focus on designing more efficient algorithms for sorting big datasets2 These datasets are often much larger than the computer's main memory and the performance bottleneck changes from being the number of CPU instructions executed to being the number of accesses to slow secondary storage. In this external memory setting, one usually uses the external memory model to analyze the performance of algorithms. External memory algorithms are designed to minimize the number of input/output (I/O)s between the internal memory and external memory (e.g., hard drives and cloud storage), and we measure the complexity of an algorithm in terms of the number of I/Os it performs.
Formally, the external memory model consists of a main memory that can hold M words of w bits each (the memory has a total of m = Mw bits), and an infinite (random access) disk partitioned into blocks of B consecutive words of w bits each (a block has a total of b = Bw bits). The input to an external memory algorithm is initially stored on disk and is assumed to be much larger than M. An algorithm can then read blocks into memory or write blocks to disk. We refer jointly to these two operations as an I/O. The complexity of an algorithm is measured solely in terms of the number of I/Os it makes.
No entries found