Selection from read-only memory with limited workspace

TY - GEN

T1 - Selection from read-only memory with limited workspace

AU - Elmasry, Amr

AU - Juhl, Daniel Dahl

AU - Katajainen, Jyrki

AU - Satti, Srinivasa Rao

N1 - Conference code: 19

PY - 2013

Y1 - 2013

N2 - In the classic selection problem the task is to find the kth smallest of N elements. We study the complexity of this problem on a space-bounded random-access machine: The input is given in a read-only array and the capacity of workspace is limited. We prove that the linear-time prune-and-search algorithm-presented in most textbooks on algorithms-can be adjusted to use O(N) bits instead of Θ(N) words of extra space. Prior to our work, the best known algorithm by Frederickson could perform the task with O(N) bits of extra space in O(N log N) time. In particular, our result separates the space-restricted random-access model and the multi-pass streaming model (since we can bypass the Ω(N log N) lower bound known for the latter model). We also generalize our algorithm for the case when the size of the workspace is O(S) bits,. The running time of our generalized algorithm is, slightly improving over the bound of Frederickson's algorithm. Of independent interest, the wavelet stack-a structure we used for repeated pruning-may also be useful in other applications.

AB - In the classic selection problem the task is to find the kth smallest of N elements. We study the complexity of this problem on a space-bounded random-access machine: The input is given in a read-only array and the capacity of workspace is limited. We prove that the linear-time prune-and-search algorithm-presented in most textbooks on algorithms-can be adjusted to use O(N) bits instead of Θ(N) words of extra space. Prior to our work, the best known algorithm by Frederickson could perform the task with O(N) bits of extra space in O(N log N) time. In particular, our result separates the space-restricted random-access model and the multi-pass streaming model (since we can bypass the Ω(N log N) lower bound known for the latter model). We also generalize our algorithm for the case when the size of the workspace is O(S) bits,. The running time of our generalized algorithm is, slightly improving over the bound of Frederickson's algorithm. Of independent interest, the wavelet stack-a structure we used for repeated pruning-may also be useful in other applications.

U2 - 10.1007/978-3-642-38768-5_15

DO - 10.1007/978-3-642-38768-5_15

M3 - Article in proceedings

SN - 978-3-642-38767-8

T3 - Lecture notes in computer science

SP - 147

EP - 157

BT - Computing and Combinatorics

A2 - Du, Ding-Zhu

A2 - Zhang, Guochuan

PB - Springer

T2 - 19th International Conference on Computing and Combinatorics

Y2 - 21 June 2013 through 23 June 2013

ER -