The space complexity of approximating the frequency moments

September 10, 2008 in algorithms, math, papers with Leave a Comment

Paper by Noga Alon, Yossi Matias and Mario Szegedy.

My reading group read this paper today. Given the authors, perhaps not surprisingly, I was thoroughly entertained.

Here is what it is about. Suppose you get to see a sequence of elements a_1, a_2, \ldots, a_n where, for i=1,\ldots,n, a_i\in \{1,2,..m\}. Let us say element j appears n_j times in the sequence. Now if you have to compute the k'th frequency moment,

F_k=\sum_{j=1}^m n_j^k,

how much space would you need to do it “on the fly”? On the fly means that elements of the sequence are revealed one at a time, and we do not get to see a past sequence element (unless we store it).

Clearly, F_1 (sequence length) can be computed in \Theta(\log n) space, incrementing by 1 each time a sequence element is revealed. Now let m\ll n and consider computing F_2. Say that at the 10′th position we saw symbol “3″. To update F_2, we have to add 2n^{'}_3+1 to the current estimate of F_2, where n^{'}_3 is the number of times 3 appeared (the frequency of 3) among the first 9 sequence symbols. Since we do not know a-priori what the 10′th element would have been, it would appear that for all k\ge2, one needs to keep track of the frequency of every symbol appearing in the sequence. If you keep track of the frequency of elements, you need {\cal O}(\log n) bits for each element that appeared. Since m\ll n, in the most inconvenient sequence all m elements appear, hence you need \Omega(m\log n) bits of memory. In general, without assuming m\ll n, it would appear that \Omega\left(\log {n+m-1 \choose m-1}\right) bits of memory are needed.

Amazingly, the authors show how to compute F_2 with just \Theta(\log n+\log m) bits, equivalently, using just enough space to keep the frequency of a constant number of elements.

Generally, for all k, the trick is to find a few random variables, each of whose expectation is F_k, and to combine them for a better estimate. There is a somewhat novel (to me) median of means approach to bootstrap the random variables for a good estimate of F_k,. But the novelty of the bootstrap pales in comparison with that of the choice of the random variables.

The crux of the approach is this cute observation (homework for you): given a sequence a_1,\ldots, a_n, pick a position {\bf P} at random from 1 through n. Let {\bf R} be the random variable that counts the number of times a_{\bf P} (the element at position {\bf P} chosen in the previous step) appears in the subsequence a_{\bf P},\ldots, a_n. What is nE({\bf R}^k-({\bf R}-1)^k)? (Notation: E denotes expectation).

Of course, once you figure that out, it is easy to see where the paper will lead. But regarding the novelty and simplicity of the paper, as the clever mechanic’s itemized bill goes, “$1 for turning the screw, $499 for knowing which one”.

Three puzzles

September 1, 2008 in communications, math, puzzles with Leave a Comment

Here are three puzzles, all closely related. Each of the puzzles can be used to explain a particular area of research. In particular, the areas are

  1. Writing on dirty paper
  2. Wiretap channel
  3. Wyner Ziv

You can however do these puzzles knowing nothing about the above areas. Future posts will give a layman’s introduction to these topics, for now, here are the puzzles.

(Writing on dirty paper) Alice and Bob want to talk with each other. But they live in the Victorian age, and the only way they can do so is through a chaperone. The chaperone writes 8 bits (0’s and 1’s) and makes Alice flip exactly one of them. How many messages can Alice send Bob? Thanks to Paul for this one.

(Wiretap channel) Alice and Bob have gone a little further now. They want to send private notes to each other but the chaperone, Eve, evesdrops on them. Eve is lazy, she figures it is enough to randomly pick parts of their communication and read it—since Alice wouldn’t know which parts Eve will read. Alice sends Bob 8 bits, and they both know Eve will read some 5 bits of that.

Alice and Bob are smarter than Eve. They realize they can still send private messages which Eve will not figure out, though they have no idea which bits Eve will read. Question is, how many such private messages?

(Wyner Ziv) Alice and Bob have a 8-bit sequence each. They know that the hamming distance between their vectors is 1, namely the sequences differ in exactly one position. But they do not know which position the sequences differ in. How many bits must Alice send so that Bob can figure out Alice’s sequence? Thanks to Alon for this one.

  • Categories

  • Posts by date

    November 2009
    M T W T F S S
    « Sep    
     1
    2345678
    9101112131415
    16171819202122
    23242526272829
    30  

  • Meta

  • Comments