<p>For k&lt;=2</p>

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

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

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

CC BY-SA 3.0
2011-12-12T02:25:31.223Z
2011-12-12T02:25:31.223Z
Ashwinkumar B V
<p>Something related.</p>

<p>I think there has also been some related work on approximating $F_\alpha$ where $\alpha$ is not necessarily a integer. <a href="http://www.stat.cornell.edu/~li/SODA09_CC.pdf" rel="nofollow">http://www.stat.cornell.edu/~li/SODA09_CC.pdf</a> 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$.</p>

CC BY-SA 3.0
2011-12-14T02:12:22.737Z
Note this is for $\alpha \in (1, 2)$ when the dependence on $n$ is known to be polylog so $\epsilon$ becomes the bottleneck
Sasho Nikolov
CC BY-SA 3.0
2011-12-13T16:06:25.913Z
2011-12-13T16:06:25.913Z
Ashwinkumar B V
<p>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 &gt; 2$. The upper bounds come from <a href="http://mit.dspace.org/bitstream/handle/1721.1/6741/AIM-2004-014.pdf?sequence=2">this paper by Indyk and Woodruff</a> (which appeared in STOC 2005) and the lower bounds are via the information complexity framework, due to <a href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.7876">Bar-Yossef et al</a> and <a href="http://ftp.cs.nyu.edu/~khot/papers/ccc03-disj.pdf">Chakrabarti et al</a>.</p>

CC BY-SA 3.0
2011-12-09T18:47:24.033Z
This is also relevant: http://arxiv.org/abs/1011.1263
Mahdi Cheraghchi
CC BY-SA 3.0
2011-12-09T20:24:57.163Z
Check the link @MCH sent, it makes the algorithm and analysis lean and mean. But maybe David's thesis will be useful for intuition and discussion, too: http://www.almaden.ibm.com/cs/people/dpwoodru/phdFinal.pdf
Sasho Nikolov
CC BY-SA 3.0
2011-12-09T08:31:26.537Z
2011-12-09T16:03:33.840Z
2011-12-09T16:03:33.840Z
Suresh Venkat
<p>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 </p>

<p>$\displaystyle F_k = \sum_{i=1}^n m_i^k.$</p>

<p>In their well-known paper, <a href="http://dl.acm.org/citation.cfm?id=237823">The space complexity of approximating the frequency moments</a>, 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 &gt; 5$. For $k = 0,1,2$, they provide more or less matching upper and lower bounds.</p>

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

<ds.algorithms><reference-request><communication-complexity><data-streams>
Bounds on approximating frequency moments
Timothy Sun
# Bounds on approximating frequency moments

(Asked by: username_0 on 2011-12-09)

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](http://dl.acm.org/citation.cfm?id=237823), 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$?

**Tags:** ds.algorithms, reference-request, communication-complexity, data-streams

---

## 3 answers

### Answer by username_3 on 2011-12-09. Score: 14 | Accepted answer

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](http://mit.dspace.org/bitstream/handle/1721.1/6741/AIM-2004-014.pdf?sequence=2) (which appeared in STOC 2005) and the lower bounds are via the information complexity framework, due to [Bar-Yossef et al](http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.7876) and [Chakrabarti et al](http://ftp.cs.nyu.edu/~khot/papers/ccc03-disj.pdf).

> **Comments:**
> **username_4**: This is also relevant: http://arxiv.org/abs/1011.1263  
> **username_2**: Check the link @MCH sent, it makes the algorithm and analysis lean and mean. But maybe David's thesis will be useful for intuition and discussion, too: http://www.almaden.ibm.com/cs/people/dpwoodru/phdFinal.pdf  

---

### Answer by username_1 on 2011-12-12. Score: 3

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


---

### Answer by username_1 on 2011-12-13. Score: 1

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$.

> **Comments:**
> **username_2**: Note this is for $\alpha \in (1, 2)$ when the dependence on $n$ is known to be polylog so $\epsilon$ becomes the bottleneck  

---

