|
Title |
Asymptotically Optimal Encodings for Range Selection |
|
Authors |
Gonzalo Navarro, Rajeev Raman, S. Srinivasa Rao |
|
Publication date |
2014 |
|
Abstract |
We consider the problem of preprocessing an array A[1..n] to answer range selection and range top-k queries. Given a query interval [i..j] and a value k, the former query asks for the position of the kth largest value in A[i..j], whereas the latter asks for the positions of all the k largest values in A[i..j]. We consider the encoding version of the problem, where A is not available at query time and a bound K is given at construction time. We obtain data structures with asymptotically optimal size and query time on a RAM model with word size Theta(lg n): our structures use O(n lg K) bits and answer range selection queries in time O(1 + lg k / lg lg n) and range top-k queries in time O(k), for any k \le K. |
|
Downloaded |
4 times |
|
Pages |
291-302 |
|
Conference name |
Annual Conference on Foundations of Software Technology and Theoretical Computer Science |
|
Publisher |
IBFI Schloss Dagstuhl (Wadern, Germany) |
|
PDF |
|
|
Reference URL |
|
