Tight results for clustering and summarizing data streams
Tight results for clustering and summarizing data streams
复制标题
聚类和汇总数据流的严格结果
DOI：
10.1145/1514894.1514926
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
S. Guha
中科院分区：
文献类型：
--
作者：
S. Guha
在本文中，我们研究算法和下界的摘要问题，在一个单一的通过数据流。特别是，我们专注于直方图的建设和K-中心聚类。我们提供了一个简单的框架，提高了所有以前的算法对这些问题的空间约束，近似因子或运行时间。该框架使用了“流引导”的概念，其中为数据的初始前缀创建的摘要用于开发更好的近似算法。我们还证明了这些问题的第一个非平凡的下界。我们表明，更严格的要求，如果一个算法准确地近似每个桶或它产生的每个集群的错误，那么这些上限几乎是最好的可能。这个属性的准确估计是真实的所有已知的上界对这些问题。
In this paper we investigate algorithms and lower bounds for summarization problems over a single pass data stream. In particular we focus on histogram construction and K-center clustering. We provide a simple framework that improves upon all previous algorithms on these problems in either the space bound, the approximation factor or the running time. The framework uses a notion of "streamstrapping" where summaries created for the initial prefixes of the data are used to develop better approximation algorithms. We also prove the first non-trivial lower bounds for these problems. We show that the stricter requirement that if an algorithm accurately approximates the error of every bucket or every cluster produced by it, then these upper bounds are almost the best possible. This property of accurate estimation is true of all known upper bounds on these problems.