Showing posts tagged streaming algorithms

Estimating the Second Frequency Moment

\(\) I just uploaded an updated version of an essay, Estimating the Second Frequency Moment.┬áThe frequency moment problem was addressed in the seminal paper of Alon, Matias and Szegedy. In my essay, I give a couple of results from that paper and give indications of how the results can be generalized. Suppose you are shown a stream of numbers \(s_1, s_2, \ldots, s_n\) where each \(s_j \in {1,2, \ldots, m}\) for \(j = 1, 2, \ldots, n\). If \(f_i\) denotes the number of times \(i…

Keep reading