[Solved]: Count-Min sketch: dyadic ranges

Problem Detail: 

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

Asked By : Erric

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/34099

 Ask a Question

 Download Related Notes/Documents