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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.