Consider a universe $\mathcal U\triangleq \{1,2,\ldots n\}$, and assume that we are given a set $S\subseteq \mathcal U$.

There are many data structures that allow storing $S$ while answering Rank queries of the form:

How many items in $S$ have identifier smaller than $i$, for some $i\in\mathcal U$? I.e., we are looking for $R_i(s)\triangleq|\{j\in S\mid j\le i\}|$.

These data structures use $n(1+o(1))$ bits and answer such queries in $O(1)$ time (we can get improved memory bounds if some bound $m<n$ is known on the set size).

Assume now that we want sub-linear space, and are willing to settle for approximate Rank queries. That is, given $i$, we want to return an estimate $\widehat{R_i(S)}$.

For some $\epsilon>0$, what is known about the size of such data structures that when queried produces estimates that satisfy ${R_i(S)}\le\widehat{R_i(S)}\le{R_i(S)}(1+\epsilon)$ in $O(1)$ time?

  • $\begingroup$ Consider $S = \{k\}$, in this case we can evaluate each $\widehat{R_i(S)}$ and for all $i < k$ we must have $\widehat{R_i(S)} = 0$ and for all $i \geq k$ we must have $\widehat{R_i(S)} > 0$ thus we can uniquely determine $k$. So as a lower bound the data structure must be able to encode an arbitrary integer up to $n$, requiring $\log n$ bits. $\endgroup$ – orlp Apr 10 '17 at 23:58
  • $\begingroup$ Streaming quantile estimation solutions like Karnin et al.'s "Optimal Quantile Approximation in Streams" provide a solution for estimating quantiles by keeping a sample of the data, but any such sample with $\omega(1)$ size will use $\omega(1)$ time to query, since predecessor queries are not constant time. $\endgroup$ – jbapple Jun 18 '17 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.