# Rank Queries of Uniformly Drawn Order Statistics

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.

• so you want sublinear space as well as sublogarithmic time ? – Suresh Venkat Jun 3 '11 at 20:45
• 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 Jun 3 '11 at 20:52
• 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 Jun 3 '11 at 21:00