Streaming K-means algorithms are applied when data comes in a stream and we want to estimate the clusters dynamically. Streaming the K-means algorithm is based on the paper Fast and Accurate K-Means for Large Datasets by M. Schindler, A. Wong, and A. Meyerson.

This paper can be found at http://papers.nips.cc/paper/4362-fast-and-accurate-k-means-for-large-datasets.pdf.

The algorithm uses the O (k logn) memory, runs in the O (nk log n) time, and obtains an O (1) worst-case approximation. The streaming step passes the clusters to the BallKMeans step. This step moves the points to the center of the mass of the samples and further reduces the number of clusters down to K.

In Mahout, Streaming K-means is implemented using two steps:

As Ted Dunning (who has contributed to Mahout clustering, classification, and matrix decomposition algorithms, and has helped expand the new version of Mahout Math library) recently mentioned (in a Mahout user group e...