Aarhus University Seal

Range Selection and Median: Tight Cell Probe Lower Bounds and Adaptive Data Structures

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
Range selection is the problem of preprocessing an input
array A of n unique integers, such that given a query (i; j; k),
one can report the k'th smallest integer in the subarray
A[i];A[i+1]; : : : ;A[j]. In this paper we consider static data
structures in the word-RAM for range selection and several
natural special cases thereof.
The rst special case is known as range median, which
arises when k is xed to b(j 􀀀 i + 1)=2c. The second
case, denoted prex selection, arises when i is xed to 0.
Finally, we also consider the bounded rank prex selection
problem and the xed rank range selection problem. In
the former, data structures must support prex selection
queries under the assumption that k for some value
n given at construction time, while in the latter, data
structures must support range selection queries where k
is xed beforehand for all queries. We prove cell probe
lower bounds for range selection, prex selection and range
median, stating that any data structure that uses S words
of space needs
(log n= log(Sw=n)) time to answer a query.
In particular, any data structure that uses n logO(1) n space
(log n= log log n) time to answer a query, and any
data structure that supports queries in constant time, needs
(1) space. For data structures that uses n logO(1) n
space this matches the best known upper bound.
Additionally, we present a linear space data structure
that supports range selection queries in O(log k= log log n +
log log n) time. Finally, we prove that any data struc-
ture that uses S space, needs
(log = log(Sw=n)) time
to answer a bounded rank prex selection query and

(log k= log(Sw=n)) time to answer a xed rank range se-
lection query. This shows that our data structure is optimal
except for small values of k.
Original languageEnglish
Title of host publicationProceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 2011
Number of pages9
PublisherSociety for Industrial and Applied Mathematics
Publication year2011
Publication statusPublished - 2011
EventSymposium on Discrete Algorithms. SODA 2011 -
Duration: 17 Dec 2010 → …
Conference number: 22


ConferenceSymposium on Discrete Algorithms. SODA 2011
Periode17/12/2010 → …

See relations at Aarhus University Citationformats

ID: 40273498