Selection from read-only memory with limited workspace

TY - JOUR

T1 - Selection from read-only memory with limited workspace

AU - Elmasry, Amr

AU - Juhl, Daniel Dahl

AU - Katajainen, Jyrki

AU - Satti, Srinivasa Rao

N1 - Computing and Combinatorics

PY - 2014

Y1 - 2014

N2 - Given an unordered array of N elements drawn from a totally ordered set and an integer k in the range from 1 to N, in the classic selection problem the task is to find the k-th smallest element in the array. We study the complexity of this problem in the space-restricted random-access model: The input array is stored on read-only memory, and the algorithm has access to a limited amount of workspace. We prove that the linear-time prune-and-search algorithm-presented in most textbooks on algorithms-can be modified to use Θ(N) bits instead of Θ(N) words of extra space. Prior to our work, the best known algorithm by Frederickson could perform the task with Θ(N) bits of extra space in O(Nlg*N) time. Our result separates the space-restricted random-access model and the multi-pass streaming model, since we can surpass the Ω(Nlg*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, where lg3N≤S≤N. The running time of our generalized algorithm is O(Nlg*(N/S)+N(lgN)/lgS), slightly improving over the O(Nlg*(N(lgN)/S)+N(lgN)/lgS) bound of Frederickson's algorithm. To obtain the improvements mentioned above, we developed a new data structure, called the wavelet stack, that we use for repeated pruning. We expect the wavelet stack to be a useful tool in other applications as well.

AB - Given an unordered array of N elements drawn from a totally ordered set and an integer k in the range from 1 to N, in the classic selection problem the task is to find the k-th smallest element in the array. We study the complexity of this problem in the space-restricted random-access model: The input array is stored on read-only memory, and the algorithm has access to a limited amount of workspace. We prove that the linear-time prune-and-search algorithm-presented in most textbooks on algorithms-can be modified to use Θ(N) bits instead of Θ(N) words of extra space. Prior to our work, the best known algorithm by Frederickson could perform the task with Θ(N) bits of extra space in O(Nlg*N) time. Our result separates the space-restricted random-access model and the multi-pass streaming model, since we can surpass the Ω(Nlg*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, where lg3N≤S≤N. The running time of our generalized algorithm is O(Nlg*(N/S)+N(lgN)/lgS), slightly improving over the O(Nlg*(N(lgN)/S)+N(lgN)/lgS) bound of Frederickson's algorithm. To obtain the improvements mentioned above, we developed a new data structure, called the wavelet stack, that we use for repeated pruning. We expect the wavelet stack to be a useful tool in other applications as well.

U2 - 10.1016/j.tcs.2014.06.012

DO - 10.1016/j.tcs.2014.06.012

M3 - Journal article

SN - 0304-3975

VL - 554

SP - 64

EP - 73

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -