7
$\begingroup$

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

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – András Salamon
    Mar 1, 2013 at 12:20

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jardine
    Mar 1, 2013 at 16:33
  • $\begingroup$ Basically a statistical language model has probabilities of the form P( this word sequence | some other word sequence) $\endgroup$
    – Suresh Venkat
    Mar 1, 2013 at 22:38

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.