Range Selection Queries in Data Aware Space and Time

摘要

On a given vector X = (x, x,..., x) of integers, the range selection (i, j, k) query is finding the k-th smallest integer in (x, x,..., x) for any (i, j, k) such that 1 ≤ i ≤ j ≤ n, and 1 ≤ k ≤ j - i + 1. Previous studies on the problem kept X intact and proposed data structures that occupied additional O(n · log n) bits of space over the X itself that answer the queries in logarithmic time. In this study, we replace X and encode all integers in it via a single wavelet tree by using S = n · log u + Σ log x + o(n · log u + Σ log x) bits, where u is the number of distinct ⌊log x⌋ values observed in X. Notice that u is at most 32 (64) for 32-bit (64-bit) integers and when x > u, the space used for x in the proposed data structure is less then the Elias-δ coding of x. Besides data-aware coding of X, the range selection is performed in O(log u + log x') time where x' is the k-th smallest integer in the queried range. This somewhat adaptive result interestingly achieves the range selection regardless of the size of X, and totally depends on the actual answer of the query. In summary, to the best of our knowledge, we present the first algorithm using data-aware space and time for the general range selection problem.