In-DBMS K-means Clustering for Binary Streams

Clustering data streams is an important problem in big data analytics to detect and monitor activity in fast-evolving environments. We thereby present efficient variants of the K-Means algorithm for finding quality clusters in one-pass, suitable for stream processing in a DBMS. Our main variants are Online K-means, Incremental K-means, and Sliding Window K-means, which can consider or ignore time decay. We then explain how to integrate our algorithms with a DBMS using a combination of SQL queries and UDFs. Acceleration is achieved through a careful combination of optimizations, including sufficient statistics (data summarization), sparse distance computation (Jaccard and Euclidean), multithreaded processing (for multi-core CPUs), and sparse matrix operations. We present benchmark experiments comparing the quality of results and speed. We show that Incremental K-Means achieves similar or even better results than the Standard K-Means algorithm. On the other hand, we show that the sliding window K-Means algorithm captures the evolution of data streams through time.