"Online k-means Clustering on Arbitrary Data Streams"
Robi Bhattacharjee (UCSD)
Monday, November 22nd 2021, 2-3pm
We propose a data parameter, P(X), such that for any algorithm maintaining O(k polylog(n)) centers at time n, there exists a data stream X for which a loss of O(P(X)) is inevitable.
We then give a randomized algorithm that achieves clustering loss O(P(X) + L(X, OPT)). Our algorithm uses O(k polylog(n)) memory and maintains O(k polylog(n)) cluster centers. Our algorithm also enjoys a running time of O(k polylog(n)) and is the first algorithm to achieve polynomial space and time complexity in this setting. It also is the first to have provable guarantees without making any assumptions on the input data.
Joint work with Sanjoy Dasgupta, Jacob Imola, and Michal Moshkovitz.