期刊
SIAM JOURNAL ON COMPUTING
卷 39, 期 3, 页码 923-947出版社
SIAM PUBLICATIONS
DOI: 10.1137/070699007
关键词
k-median clustering; k-means clustering; coreset; random sampling; high dimensions; approximation algorithms
We present new approximation algorithms for the k-median and k-means clustering problems. To this end, we obtain small coresets for k-median and k-means clustering in general metric spaces and in Euclidean spaces. In R-d, these coresets are of size with polynomial dependency on the dimension d. This leads to (1 + epsilon)-approximation algorithms to the optimal k-median and k-means clustering in Rd, with running time O(ndk + 2((k/epsilon)O(1)) d(2) log(k+2) n), where n is the number of points. This improves over previous results. We use those coresets to maintain a (1 + epsilon)-approximate k-median and k-means clustering of a stream of points in R-d, using O(d(2)k(2)epsilon(-2) log(8) n) space. These are the first streaming algorithms, for those problems, that have space complexity with polynomial dependency on the dimension.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据