## P. Agarwal, G. Cormode, Z. Huang, J. Phillips, Z. Wei, and K. Yi.
Mergeable coresets.
In *Third Workshop on Massive Data Algorithmics (MASSIVE)*, 2011.

We study the *mergeability* of data summaries. Informally speaking,
mergeability requires that, given two summaries on two data sets, there is
a way to merge the two summaries into a summary on the two data sets
combined together, while preserving the error and size guarantees. This
property means that the summary can be treated like other algebraic
objects such as sum and max,
which is especially useful for computing summaries on massive distributed
data. Many data summaries are trivially mergeable by construction, most
notably those based on linear transformations. But some other fundamental
ones like those for heavy hitters and quantiles, are not (known to be)
mergeable. In this paper, we demonstrate that these summaries are indeed
mergeable or can be made mergeable after appropriate modifications.
Specifically, we show that for ε-approximate heavy hitters, there is a
deterministic mergeable summary of size *O*(1/ε); for ε-approximate
quantiles, there is a deterministic summary of size *O*((1)/(ε)
log(ε*n*)) that has a restricted form of mergeability, and a randomized
one of size *O*((1)/(ε) log^{3/2}(1)/(ε)) with full
mergeability. We also extend our results to geometric summaries such as
ε-approximations and ε-kernels.

[ bib |
.pdf ]
Back

*This file was generated by
bibtex2html 1.92.*