<p>$F_0$ counting (or estimating distinct elements, or "cardinality estimation") is very useful. </p>

<p>Example: when you're doing profiling at the router level, you often want to estimate functions of distinct IP addresses, and since you can't just maintain counters for each possible address, $F_0$ counting turns out to be quite useful.</p>

<p>$F_1$ counting, or frequency estimation is also very useful:</p>

<p>Example: There's work on building statistical language models that involve counting frequencies of pairs of words, triples of words, and so on. You can't maintain counts for all such triples, so you often want "frequent" ones, or "heavy hitters". </p>

CC BY-SA 3.0
2013-03-01T16:33:29.830Z
many thanks for your answer.  i was more interested to know about higher moments. also, can you please give me some pointers or explain about 'statistical language models'? what are these? are you talking about NLP applications? i am looking for connections to statistics as an area of mathematics, as mentioned in bold letters.
Jardine
CC BY-SA 3.0
2013-03-01T22:38:33.117Z
Basically a statistical language model has probabilities of the form P( this word sequence | some other word sequence)
Suresh Venkat
CC BY-SA 3.0
2013-03-01T13:29:47.160Z
2013-03-01T13:29:47.160Z
Suresh Venkat
<p>The celebrated AMS paper "The space complexity of approximating the frequency moments" defines the problem as following:</p>

<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 kth frequency moment is defined to be</p>

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

<p>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>There have been more work in this area which have improved upon the results of this paper:</p>

<p>For $F_k$, there is a matching upper and lower bound of $n^{1−2/k}$ for $k&gt;2$. The upper bounds are 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.</p>

<p>There has also been some related work on approximating $F_\alpha$ where $\alpha$ is not necessarily an integer. <a href="http://www.stat.cornell.edu/~li/SODA09_CC.pdf" rel="nofollow noreferrer">http://www.stat.cornell.edu/~li/SODA09_CC.pdf</a> </p>

<p>This question talks about the improvements: <a href="https://cstheory.stackexchange.com/questions/9358/bounds-on-approximating-frequency-moments">Bounds on approximating frequency moments</a></p>

<p>My question is regarding the motivations of this line of work. The AMS paper talks about the application of $F_2$ to compute the surprise index, the moments give the skewness of the data which helps to select appropriate algorithm for data partitioning of a database. Other sources and papers mention applications in databases. </p>

<p>Other than these, is there any motivation for using these moment estimating algorithms in statistics? What I am thinking about is <strong>how relevant is this line of work to the statistics community?</strong>
I was presuming a scenario that these moments may be useful to compute some statistic of the data for some statistical estmation or test of hypothesis, but if they use higher moments like k>6, the linear lower bounds on space motivate the approximation of such statistic using only lower moments or formulation of different statistic that uses only lower moments which can be computed in sublinear space. But, I am not aware of such scenario and couldnt find one. Can you please help me find?</p>

<p>[Though not sure, I presume using estimates of these moments,  one can also approximate central moments. <strong>Please comment and correct me on this as well.</strong>] </p>

<p><strong>Also, if you add any motvation not mentioned here, it will be heplful.</strong>
<em>Please dont hesitate to improve my question.</em></p>

CC BY-SA 3.0
2013-03-01T12:20:13.360Z
I think it is hard to argue that $n^{1/3}$ is fine but $n^{5/7}$ is not.  Streaming lower bounds seem meant to be interesting when even the $n^{1/3}$ bound is too large for practical use.  So such bounds are really evidence that certain kinds of problems cannot be done using streaming approaches, even approximately; instead we need to look for other methods.
András Salamon
<ds.algorithms><communication-complexity><st.statistics><data-streams><streaming>
Streaming Algorithms: Motivations for estimating frequency moments
Jardine
# Streaming Algorithms: Motivations for estimating frequency moments

(Asked by: username_0 on 2013-03-01)

The celebrated AMS paper "The space complexity of approximating the frequency moments" defines the problem as following:

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 kth frequency moment is defined to be

$$\displaystyle F\_k = \sum\_{i=1}^n m\_i^k.$$

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.

There have been more work in this area which have improved upon the results of this paper:

For $F\_k$, there is a matching upper and lower bound of $n^{1−2/k}$ for $k>2$. The upper bounds are 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.

There has also been some related work on approximating $F\_\alpha$ where $\alpha$ is not necessarily an integer. <http://www.stat.cornell.edu/~li/SODA09_CC.pdf>

This question talks about the improvements: [Bounds on approximating frequency moments](https://cstheory.stackexchange.com/questions/9358/bounds-on-approximating-frequency-moments)

My question is regarding the motivations of this line of work. The AMS paper talks about the application of $F\_2$ to compute the surprise index, the moments give the skewness of the data which helps to select appropriate algorithm for data partitioning of a database. Other sources and papers mention applications in databases.

Other than these, is there any motivation for using these moment estimating algorithms in statistics? What I am thinking about is **how relevant is this line of work to the statistics community?**
I was presuming a scenario that these moments may be useful to compute some statistic of the data for some statistical estmation or test of hypothesis, but if they use higher moments like k>6, the linear lower bounds on space motivate the approximation of such statistic using only lower moments or formulation of different statistic that uses only lower moments which can be computed in sublinear space. But, I am not aware of such scenario and couldnt find one. Can you please help me find?

[Though not sure, I presume using estimates of these moments, one can also approximate central moments. **Please comment and correct me on this as well.**]

**Also, if you add any motvation not mentioned here, it will be heplful.**
*Please dont hesitate to improve my question.*

**Tags:** ds.algorithms, communication-complexity, st.statistics, data-streams, streaming
> **Comments:**
> **username_1**: I think it is hard to argue that $n^{1/3}$ is fine but $n^{5/7}$ is not.  Streaming lower bounds seem meant to be interesting when even the $n^{1/3}$ bound is too large for practical use.  So such bounds are really evidence that certain kinds of problems cannot be done using streaming approaches, even approximately; instead we need to look for other methods.  

---

## 1 answers

### Answer by username_2 on 2013-03-01. Score: 6

$F\_0$ counting (or estimating distinct elements, or "cardinality estimation") is very useful.

Example: when you're doing profiling at the router level, you often want to estimate functions of distinct IP addresses, and since you can't just maintain counters for each possible address, $F\_0$ counting turns out to be quite useful.

$F\_1$ counting, or frequency estimation is also very useful:

Example: There's work on building statistical language models that involve counting frequencies of pairs of words, triples of words, and so on. You can't maintain counts for all such triples, so you often want "frequent" ones, or "heavy hitters".

> **Comments:**
> **username_0**: many thanks for your answer.  i was more interested to know about higher moments. also, can you please give me some pointers or explain about 'statistical language models'? what are these? are you talking about NLP applications? i am looking for connections to statistics as an area of mathematics, as mentioned in bold letters.  
> **username_2**: Basically a statistical language model has probabilities of the form P( this word sequence | some other word sequence)  

---

