Lower bounds for external memory integer sorting via network coding

DOI10.1145/3313276.3316337zbMATH Open1433.68110arXiv1811.01313OpenAlexW2964250714MaRDI QIDQ5212840FDOQ5212840

Authors: Alireza Farhadi, Kasper Green Larsen, Elaine Shi, Mohammad T. Hajiaghayi 

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: Sorting extremely large datasets is a frequently occuring 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 (1988), 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 $Theta(lgn)$ 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. 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 limitations, especially for integer sorting: we show that the Li and Li conjecture implies an $Omega(nlogn)$ lower bound for internal memory oblivious sorting when the keys are $Theta(lgn)$ bits. This is in sharp contrast to the classic (non-oblivious) Radix Sort algorithm. Indeed going beyond obliviousness is highly non-trivial; 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.

Full work available at URL: https://arxiv.org/abs/1811.01313

Recommendations

• Lower bounds for external memory integer sorting via network coding
• RAM-efficient external memory sorting
• scientific article; zbMATH DE number 4020488
• Lower bounds for external algebraic decision trees
• RAM-efficient external memory sorting

zbMATH Keywords

lower boundsreductionsnetwork codingexternal memoryinteger sorting

Mathematics Subject Classification ID

Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (7)

• OptORAMa: optimal oblivious RAM
• Is there an oblivious RAM lower bound for online reads?
• OptORAMa: Optimal oblivious RAM
• A logarithmic lower bound for oblivious RAM (for all Parameters)
• A theory of composition for differential obliviousness
• Lower Bounds for Multiplication via Network Coding
• Sorting Short Keys in Circuits of Size ${o(n \log n)}$

This page was built for publication: Lower bounds for external memory integer sorting via network coding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212840)