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

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

<blockquote>
  <p>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\}|$.</p>
</blockquote>

<p>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&lt;n$ is known on the set size).</p>

<hr>

<p>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)}$.</p>

<blockquote>
  <p><strong>For some $\epsilon&gt;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?</strong></p>
</blockquote>

CC BY-SA 3.0
2017-04-10T23:58:34.840Z
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.
orlp
CC BY-SA 3.0
2017-06-18T18:57:50.270Z
Streaming quantile estimation solutions like [Karnin et al.'s "Optimal Quantile Approximation in Streams"](https://arxiv.org/abs/1603.05346) 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.
jbapple
<ds.algorithms><approximation-algorithms><ds.data-structures><encoding>
What is known about data structures for encoding a set while considering approximate Rank queries?
R B
# What is known about data structures for encoding a set while considering approximate Rank queries?

(Asked by: username_0 on 2017-04-06)

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

---

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?**

**Tags:** ds.algorithms, approximation-algorithms, ds.data-structures, encoding
> **Comments:**
> **username_1**: 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.  
> **username_2**: Streaming quantile estimation solutions like [Karnin et al.'s "Optimal Quantile Approximation in Streams"](https://arxiv.org/abs/1603.05346) 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.  

---

## 0 answers

