"Divide and conquer" data stream algorithms 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)
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.