12
$\begingroup$

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)

Improve this question
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Thomas Ahle
    Commented May 3, 2016 at 14:35

6 Answers 6

Reset to default
9
$\begingroup$

Guha et al. '03 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.

Improve this answer
$\endgroup$
0
7
$\begingroup$

The paper by Bagchi, Chaudhary, Eppstein and Goodrich 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.

Improve this answer
$\endgroup$
6
$\begingroup$

I've found a paper ("Distributing Frequency-Dependent Data Stream Computations") 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") whose main result is used as the basis for this one.

This reminds me of the Third Homomorphism Theorem...

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Sep 16, 2010 at 4:58
  • $\begingroup$ Upon reading it seems to me that it does not use multiple passes after all. $\endgroup$
    – jkff
    Commented Sep 16, 2010 at 9:51
4
$\begingroup$

Research on continuous stream query languages might provide some insight. One such a language is CQL, 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 provides a recent overview of the language, including some examples. This paper 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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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) $\endgroup$
    – jkff
    Commented Sep 17, 2010 at 4:12
3
$\begingroup$

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. One paper is this.

Ganguly's paper is very interesting, too.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.