<p>Put a uniform distribution on the integers $\{1,\cdots, M\}$. Draw $N$ samples, and sort them as $x_1 \leq \cdots \leq x_N$. A <em>rank query</em> calculates $rank(j) = \mbox{card} \{ i : x_i \leq x_j \}$ for any $1 \leq j \leq N$. </p>

<p>What is the most space-efficient data structure that can handle rank queries in constant time (or perhaps $O(\log\log N)$ time)?</p>

<p>I think that for $M = N$ it is possible to use an Elias-Fano representation to obtain the structure with $2N + o(N)$ bits of space. Can one exploit the uniform distribution assumption to do better? I am also very interested in the $M &gt; N^2$ case, which is the transition where "birthday collisions" $x_i = x_j, i \neq j$ are no longer expected.</p>

CC BY-SA 3.0
2011-06-03T20:45:53.110Z
so you want sublinear space as well as sublogarithmic time ?
Suresh Venkat
CC BY-SA 3.0
2011-06-03T20:52:37.567Z
Yes, I'm quite demanding, aren't I? :) But my understanding is the Elias-Fano representation allows this for $M=N$. I could be mistaken.
Shaun Harker
CC BY-SA 3.0
2011-06-03T21:00:49.897Z
Of course if there is some extra compression you can get by allowing log time, I guess I want to hear about that as well.
Shaun Harker
<ds.data-structures>
Rank Queries of Uniformly Drawn Order Statistics
Shaun Harker
# Rank Queries of Uniformly Drawn Order Statistics

(Asked by: username_0 on 2011-06-03)

Put a uniform distribution on the integers $\{1,\cdots, M\}$. Draw $N$ samples, and sort them as $x\_1 \leq \cdots \leq x\_N$. A *rank query* calculates $rank(j) = \mbox{card} \{ i : x\_i \leq x\_j \}$ for any $1 \leq j \leq N$.

What is the most space-efficient data structure that can handle rank queries in constant time (or perhaps $O(\log\log N)$ time)?

I think that for $M = N$ it is possible to use an Elias-Fano representation to obtain the structure with $2N + o(N)$ bits of space. Can one exploit the uniform distribution assumption to do better? I am also very interested in the $M > N^2$ case, which is the transition where "birthday collisions" $x\_i = x\_j, i \neq j$ are no longer expected.

**Tags:** ds.data-structures
> **Comments:**
> **username_1**: so you want sublinear space as well as sublogarithmic time ?  
> **username_0**: Yes, I'm quite demanding, aren't I? :) But my understanding is the Elias-Fano representation allows this for $M=N$. I could be mistaken.  
> **username_0**: Of course if there is some extra compression you can get by allowing log time, I guess I want to hear about that as well.  

---

## 0 answers

