Continuous Clustering

Question

So I have an issue I'm facing in regards to clustering with live, continuously streaming data. Since I have an ever-growing data set I'm not sure what is the best way to run efficient and effective clustering. I've come up with a few possible solutions including:

1. Setting a limit on how many data points to allow, thus whenever the limit is reached as another data point comes in the oldest point is removed. Essentially, this would suggest that older data isn't relevant enough to us anymore to care what we're losing by throwing it out.

2. Once there is enough data to make a good clustering, consider this "the setup" and as new points come, rather than re-clustering all the data just figure out which cluster center the new point is closest to and add it to that. The benefit here is you could avoid having to re-cluster on every new point and you wouldn't have to store all the other points, just the cluster centers, considering this clustering "good enough". The downside is that re-running the algorithm with all data points from the beginning may be more accurate.

While those are some potential solutions I brain-stormed, I'd like to know if there are any better known techniques to face this problem. I figure sites like Google had to deal with it somehow (and I'm hoping that "add more ram, servers and processors" or "continually expand your data centers" aren't the only answers available).

Answer 1

It sounds like you're looking for online algorithms for clustering.

I suggest searching for "online clustering" on Google Scholar. Maybe the following links will prove useful (at least as a starting point).

• Guha et al.: Clustering Data Streams: Theory and Practice
• Beringer and Hüllermeier: Online clustering of data streams

Answer 2

There's a fair amount of work on stream clustering (which is slightly different to online methods, but is essentially what you want). The above reference by Guha et al is a very good one, and for a more general perspective on what kinds of techniques work, and what methods have been used in the past (both heuristic and precise), you might want to look at my survey on clustering on streams.

Answer 3

You can also take a look at the notes for Lecture 14 and Lecture 15 of my course on data stream algorithms.

Answer 4

I like Suresh's survey above, and summarizes different approaches in stream clustering. You didnt ask for this, but it is possible in some cases, the problem is that the continuous data is seen by distributed servers, one has to maintain a clustering at the center, and not have to move a lot of data around. See here.