2
$\begingroup$

Can anyone give me a proof as to why

Any range over a unviverse {1...n} can be reduced to at most $2log_2n$ disjoint dyadic ranges?

Where a dyadic range is a range of the form $[x2^y+1....(x+1)2^y]$.

This is in reference to the method for answering range queries with a Count-Min Sketch as mentioned in the original paper on CM-sketches

$\endgroup$
2
$\begingroup$

Here is proof by example: $$ \begin{align*} &[0110000,1101011] = \\ &[0110000,0110000] \cup \\ &[0110001,1000000] \cup \\ &[1000001,1100000] \cup \\ &[1100001,1101000] \cup \\ &[1101001,1101010] \cup \\ &[1101011,1101011] \end{align*} $$ More generally, the first step is to decompose your range $[a,b]$ into $[a,2^k] \cup [2^k+1,b]$, where $b < 2^{k+1}$ (one of the ranges can be empty). Writing $b = 2^k + 2^{t_0} + \cdots + 2^{t_d}$, where $k > t_0 > \cdots > t_d$, we decompose $[2^k+1,b]$ as follows: $$ [2^k+1,b] = [2^k+1, 2^k+2^{t_0}] \cup [2^k+2^{t_0}+1,2^k+2^{t_0}+2^{t_1}] \cup \cdots \cup [2^k + 2^{t_0} + \cdots + 2^{t_{d-1}}+1, 2^k + 2^{t_0} + \cdots + 2^{t_d}]. $$ Decomposing $[a,2^k]$ into dyadic ranges is similar but slightly more confusing, and I leave it to you.

$\endgroup$
  • $\begingroup$ This seems to be the right way to go about it, and although I'm very much convinced that it can certainly be decomposed, my doubt is about the bound $2log_2n$. Could you point out when I would be needing $2log_2n$? $\endgroup$ – Erric Dec 10 '14 at 7:19
  • $\begingroup$ You need at most $\log_2 n$ to decompose each of the two halves. Here $\log_2 n$ is the maximal number of 1s in the binary representation. The bound can probably be improved slightly, though it shouldn't be hard to find examples which need $2\log_2 n - C$ ranges, for some small constant $C$. $\endgroup$ – Yuval Filmus Dec 10 '14 at 7:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.