Range Selection And Predecessor Queries In Data Aware Space And Time

Keywords

Data compression; Data structures; Predecessor search; Range searching

Abstract

On a given vector X=〈x1,x2,…,xn〉 of integers, the range selection (i,j,k) query is finding the k-th smallest integer in 〈xi,xi+1,…,xj〉 for any (i,j,k) such that 1≤i≤j≤n, and 1≤k≤j−i+1. Previous studies on the problem 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⁡xi+o(n⋅log⁡u+∑log⁡xi) bits, where u is the number of distinct ⌊log⁡xi⌋ values observed in X. Notice that u is at most 32 (64) for 32-bit (64-bit) integers and when xi>u, the space used for xi in the proposed data structure is less than the Elias-δ coding of xi. 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 result is adaptive and achieves the range selection regardless of the size of X, and the time-complexity depends on the answer itself. Additionally, we can answer range predecessor queries (i,j,x′): return the largest element y≤x′ in 〈xi,xi+1,…,xj〉, in O(log⁡u+log⁡x′) time. In summary, to the best of our knowledge, we present the first algorithms using data-aware space and time for the general range selection and predecessor problems.

Publication Date

3-1-2017

Publication Title

Journal of Discrete Algorithms

Volume

43

Number of Pages

18-25

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.jda.2017.01.002

Socpus ID

85013127810 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85013127810

This document is currently not available here.

Share

COinS