<p>I've found a paper (<a href="http://crpit.com/confpapers/CRPITV94Ganguly.pdf">"Distributing Frequency-Dependent Data Stream Computations"</a>) that says that <strong>every function of the stream's frequency distribution is mergeable</strong> (though it does not give an explicit <em>and efficient</em> construction for the merge operation). And the proof seems to be very interesting, involving some ring theory. Need to read the previous paper by the same author (<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.161.9264&amp;rep=rep1&amp;type=pdf">"Lower bounds on frequency estimation of data streams"</a>) whose main result is used as the basis for this one.</p>

<p>This reminds me of the <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.2247&amp;rep=rep1&amp;type=pdf">Third Homomorphism Theorem</a>... </p>

CC BY-SA 2.5
2010-09-16T04:58:06.167Z
I don't think the Ganguly paper implies that a divide and conquer strategy can work for streaming. That model seems to reduce to the Mapreduce/MUD model, in which there could be multiple passes over the data.
Suresh Venkat
CC BY-SA 2.5
2010-09-16T09:51:32.267Z
Upon reading it seems to me that it does not use multiple passes after all.
jkff
CC BY-SA 2.5
2010-09-15T19:59:07.240Z
2010-09-15T19:59:07.240Z
jkff
<p>The paper by <a href="http://arxiv.org/abs/cs.CG/0307027">Bagchi, Chaudhary, Eppstein and Goodrich</a> solves a number of streaming geometric problems using an underlying subroutine for computing $\varepsilon$-nets and $\varepsilon$-approximations of appropriately chosen range spaces. This subroutine makes use of the additive structure of these objects by developing a hierarchical scheme to compute them (where the virtual $i^{\text{th}}$ level stream aggregates the blocks in the virtual $(i-1)^{\text{th}}$-level stream, and level 0 is the original stream). This is essentially a bottom up rendering of a divide and conquer strategy. with updates along the "edge" of the recursion tree. In structure, it's very similar to the Guha et al paper mentioned by Lev. </p>

CC BY-SA 2.5
2010-09-14T14:27:10.130Z
2010-09-14T14:27:10.130Z
Suresh Venkat
<p>This question seems a bit circular to me. If the problem has the property you want, then there is a sketch-and-merge based algorithm for it. As mentioned above, there is work on clustering, approximations, and coresets that provide you with that. Also, most streaming algorithms allow merging streams by just (conceptually) concatenating one stream to the other.</p>

<p>Also, I am not sure top-k streaming algorithms are mergable - but I might be wrong.</p>

CC BY-SA 2.5
2010-09-17T04:12:31.517Z
Top-k are mergeable trivially: to merge two lists of k items, you merge them and take k last items of the result :) However, perhaps you meant "top k most frequent", but I meant this one (which is also a useful problem, for example, for distributed computation of something like a facebook wall)
jkff
CC BY-SA 2.5
2010-09-17T03:55:23.473Z
2010-09-17T03:55:23.473Z
Sariel Har-Peled
<p>Research on continuous stream query languages might provide some insight. One such a language is <a href="http://infolab.stanford.edu/~widom/cql-talk.pdf" rel="nofollow">CQL</a>, which I believe is being adopted by Oracle. The languages allow functions to be computed over sliding windows of the stream (including windows of size 1). This <a href="http://user.it.uu.se/~udbl/Theses/RobertKajicBSc.pdf" rel="nofollow">bachelor's thesis</a> provides a recent overview of the language, including some examples. This <a href="http://web.science.mq.edu.au/~rdale/teaching/itec810/2009H1/WorkshopPapers/Dylan_Miran_FinalWorkShopPaper.pdf" rel="nofollow">paper</a> gives an overview of some stream processing languages, which should be useful for finding links to other related research.</p>

<p>I know that this doesn't answer your question directly, but it should put you in touch with research done by people departing from the same starting point.</p>

CC BY-SA 2.5
2010-09-15T20:18:36.137Z
2010-09-15T20:18:36.137Z
Dave Clarke
<p>Sorry to be necromancing on this, but I thought you might want to look at some work on distributed continuous monitoring on streams, where you are given several streams and the goal is to monitor some aggregate statistic at a central monitoring site while minimizing communication. The model sounds to me closely related to your motivation. Look at the references in <a href="http://books.google.com/books?id=415loiMd_c0C&amp;lpg=PA1&amp;ots=Jw1evzIjNh&amp;lr&amp;pg=PA99#v=onepage&amp;q&amp;f=false" rel="nofollow">Muthu's book</a>. One paper is <a href="http://dx.doi.org/10.1145/1066157.1066161" rel="nofollow">this</a>.</p>

<p>Ganguly's paper is very interesting, too.</p>

CC BY-SA 3.0
2011-05-10T17:19:16.037Z
2011-05-10T17:19:16.037Z
Sasho Nikolov
<p><a href="http://www.computer.org/portal/web/csdl/doi/10.1109/TKDE.2003.1198387">Guha et al. '03</a> give an approximation algorithm for k-median clustering in the streaming model.  Their algorithm divides the data into disjoint pieces, finds O(k) centers for each disjoint piece, and then combines the results to get the k centers.  This seems to be the type of algorithm you're looking for.</p>

CC BY-SA 2.5
2010-09-14T11:45:28.573Z
2010-09-14T13:25:36.137Z
2010-09-14T13:25:36.137Z
Lev Reyzin
<p>What useful algorithms do there exist that work on huge data streams and also their results are fairly small and one can compute the result for a mixture of two streams by somehow merging their results?</p>

<p>I can name a few:</p>

<ul>
<li>The obvious things like sum, min, max, count, top-K etc.</li>
<li>Approximate so called "sketch-based" stream algorithms for histograms, counting distinct items or computing quantiles</li>
</ul>

<p>What others are there?</p>

<p>(I'm interested because I'm writing a hobby project for monitoring distributed systems whose usefulness is directly determined by the usefulness of such algorithms)</p>

CC BY-SA 3.0
2016-05-03T14:35:09.247Z
I find it much harder to think of any streaming algorithm that isn't "divide and conquer"/associative. Maybe some kind of rolling hash function... Do you have any natural examples of such a stream algorithm?
Thomas Ahle
<ds.algorithms><big-list><data-streams>
"Divide and conquer" data stream algorithms
jkff
# "Divide and conquer" data stream algorithms

(Asked by: username_0 on 2010-09-14)

What useful algorithms do there exist that work on huge data streams and also their results are fairly small and one can compute the result for a mixture of two streams by somehow merging their results?

I can name a few:

* The obvious things like sum, min, max, count, top-K etc.
* Approximate so called "sketch-based" stream algorithms for histograms, counting distinct items or computing quantiles

What others are there?

(I'm interested because I'm writing a hobby project for monitoring distributed systems whose usefulness is directly determined by the usefulness of such algorithms)

**Tags:** ds.algorithms, big-list, data-streams

> **Comments:**
> **username_1**: I find it much harder to think of any streaming algorithm that isn't "divide and conquer"/associative. Maybe some kind of rolling hash function... Do you have any natural examples of such a stream algorithm?  

---

## 6 answers

### Answer by username_6 on 2010-09-14. Score: 9 | Accepted answer

[Guha et al. '03](http://www.computer.org/portal/web/csdl/doi/10.1109/TKDE.2003.1198387) give an approximation algorithm for k-median clustering in the streaming model. Their algorithm divides the data into disjoint pieces, finds O(k) centers for each disjoint piece, and then combines the results to get the k centers. This seems to be the type of algorithm you're looking for.


---

### Answer by username_2 on 2010-09-14. Score: 7

The paper by [Bagchi, Chaudhary, Eppstein and Goodrich](http://arxiv.org/abs/cs.CG/0307027) solves a number of streaming geometric problems using an underlying subroutine for computing $\varepsilon$-nets and $\varepsilon$-approximations of appropriately chosen range spaces. This subroutine makes use of the additive structure of these objects by developing a hierarchical scheme to compute them (where the virtual $i^{\text{th}}$ level stream aggregates the blocks in the virtual $(i-1)^{\text{th}}$-level stream, and level 0 is the original stream). This is essentially a bottom up rendering of a divide and conquer strategy. with updates along the "edge" of the recursion tree. In structure, it's very similar to the Guha et al paper mentioned by Lev.


---

### Answer by username_0 on 2010-09-15. Score: 6

I've found a paper (["Distributing Frequency-Dependent Data Stream Computations"](http://crpit.com/confpapers/CRPITV94Ganguly.pdf)) that says that **every function of the stream's frequency distribution is mergeable** (though it does not give an explicit *and efficient* construction for the merge operation). And the proof seems to be very interesting, involving some ring theory. Need to read the previous paper by the same author (["Lower bounds on frequency estimation of data streams"](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.161.9264&rep=rep1&type=pdf)) whose main result is used as the basis for this one.

This reminds me of the [Third Homomorphism Theorem](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.2247&rep=rep1&type=pdf)...

> **Comments:**
> **username_2**: I don't think the Ganguly paper implies that a divide and conquer strategy can work for streaming. That model seems to reduce to the Mapreduce/MUD model, in which there could be multiple passes over the data.  
> **username_0**: Upon reading it seems to me that it does not use multiple passes after all.  

---

### Answer by username_3 on 2010-09-17. Score: 4

This question seems a bit circular to me. If the problem has the property you want, then there is a sketch-and-merge based algorithm for it. As mentioned above, there is work on clustering, approximations, and coresets that provide you with that. Also, most streaming algorithms allow merging streams by just (conceptually) concatenating one stream to the other.

Also, I am not sure top-k streaming algorithms are mergable - but I might be wrong.

> **Comments:**
> **username_0**: Top-k are mergeable trivially: to merge two lists of k items, you merge them and take k last items of the result :) However, perhaps you meant "top k most frequent", but I meant this one (which is also a useful problem, for example, for distributed computation of something like a facebook wall)  

---

### Answer by username_4 on 2010-09-15. Score: 4

Research on continuous stream query languages might provide some insight. One such a language is [CQL](http://infolab.stanford.edu/~widom/cql-talk.pdf), which I believe is being adopted by Oracle. The languages allow functions to be computed over sliding windows of the stream (including windows of size 1). This [bachelor's thesis](http://user.it.uu.se/~udbl/Theses/RobertKajicBSc.pdf) provides a recent overview of the language, including some examples. This [paper](http://web.science.mq.edu.au/~rdale/teaching/itec810/2009H1/WorkshopPapers/Dylan_Miran_FinalWorkShopPaper.pdf) gives an overview of some stream processing languages, which should be useful for finding links to other related research.

I know that this doesn't answer your question directly, but it should put you in touch with research done by people departing from the same starting point.


---

### Answer by username_5 on 2011-05-10. Score: 3

Sorry to be necromancing on this, but I thought you might want to look at some work on distributed continuous monitoring on streams, where you are given several streams and the goal is to monitor some aggregate statistic at a central monitoring site while minimizing communication. The model sounds to me closely related to your motivation. Look at the references in [Muthu's book](http://books.google.com/books?id=415loiMd_c0C&lpg=PA1&ots=Jw1evzIjNh&lr&pg=PA99#v=onepage&q&f=false). One paper is [this](http://dx.doi.org/10.1145/1066157.1066161).

Ganguly's paper is very interesting, too.


---

