# Avoiding cluster recalculation in large scale clustering

I am working with a large dataset containing about 500 million records and about 50 discrete dimensions. I am planning to cluster these records into a number of distinct clusters (~30). Now, every day, for a number of these records, some dimensions will change. Given that the initial clustering will take quite a bit of time, I am looking for a way to avoid running complete reclustering every day, in order to accomodate for changed records. I suppose that in most cases, for an algorithm that permits it, starting the run from previous converged solution would allow convergence to a new solution in hopefully only few iteration.

Is there a specific algorithm (preferably one that allows membership in multiple clusters) that would be useful in this case, or a trick that can help me avoid full recalculation?

• I would need some more details about your problem to say for sure, but many clustering algorithms do their clustering based on the distance between items. If that's how clustering will work here. The easiest way it probably to just save the distance matrix between runs. When data points change, you can recalculate the distance between the $m << n$ points that change with all $n$ points. If you use a clustering algorithm like $k$-means, you can initialize today's clustering with yesterday's centroids to speed it up. – Ben Oct 14 '15 at 13:33
• Can you define "some" dimensions? How many are you talking about? Also, you can simplify your life by taking samples of the 500 million records and projecting results to the remainder. This would also afford an opportunity to cross-validate the results in terms of classification (or misclassification)... – Mike Hunter Oct 14 '15 at 13:33