Settling Time vs. Accuracy Tradeoffs for Clustering Big Data

arXiv:2404.01936v1 Announce Type: new
Abstract: We study the theoretical and practical runtime limits of k-means and k-median clustering on large datasets. Since effectively all clustering methods are slower than the time it takes to read the dataset, the fastest approach is to quickly compress the data and perform the clustering on the compressed representation. Unfortunately, there is no universal best choice for compressing the number of points - while random sampling runs in sublinear time and coresets provide theoretical guarantees, …

abstract accuracy arxiv big big data clustering cs.ds cs.lg data dataset datasets k-means large datasets practical study type