Let $a_1, a_2,\dotsc, a_m$ be a sequence of integers where each $a_j \in \{1,2,\dotsc,n\}$. For $i \in \{1,2,\dotsc,n\}$, let $m_i = |\{j : a_j = i\}|$. The $k$th frequency moment is defined to be

$\displaystyle F_k = \sum_{i=1}^n m_i^k.$

In their well-known paper, The space complexity of approximating the frequency moments, Alon et al. give a streaming algorithm that approximates $F_k$ using roughly $O(n^{1-\frac{1}{k}}(\log n + \log m))$ space. They also use communication complexity techniques to obtain a lower bound of $\Omega(n^{1-\frac{5}{k}})$ for $k > 5$. For $k = 0,1,2$, they provide more or less matching upper and lower bounds.

Have there been improvements to these bounds since then, and has there been progress for $k = 3,4,5$?


There's been a fair bit of progress. On the specific problem of $F_k$, there is a matching upper and lower bound of $n^{1-2/k}$ for $k > 2$. The upper bounds come from this paper by Indyk and Woodruff (which appeared in STOC 2005) and the lower bounds are via the information complexity framework, due to Bar-Yossef et al and Chakrabarti et al.


For k<=2

1) k=0, the bound is $O(1/\epsilon^2+log(n))$ from http://people.seas.harvard.edu/~minilek/papers/f0.pdf.

2) k=1, The paper by Alon et all gives a reference to paper by Morris which takes $\tilde{O}(log(log(n))$ space.

3) k=2, I think the AMS sketch from their paper is optimal


Something related.

I think there has also been some related work on approximating $F_\alpha$ where $\alpha$ is not necessarily a integer. http://www.stat.cornell.edu/~li/SODA09_CC.pdf is something which I know of. I am not completely familiar with this but I think their main point of interest is dependence on $\epsilon$ and not $n$.

  • 1
    $\begingroup$ Note this is for $\alpha \in (1, 2)$ when the dependence on $n$ is known to be polylog so $\epsilon$ becomes the bottleneck $\endgroup$ – Sasho Nikolov Dec 14 '11 at 2:12

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.