Mergeable summaries
Abstract
We study the mergeability of data summaries. Informally speaking, mergeability requires that, given two summaries on two datasets, there is a way to merge the two summaries into a single summary on the two datasets combined together, while preserving the error and size guarantees. This property means that the summaries can be merged in a way akin to other algebraic operators such as sum and max, which is especially useful for computing summaries on massive distributed data. Several data summaries are trivially mergeable by construction, most notably all the sketches that are linear functions of the datasets. But some other fundamental ones, like those for heavy hitters and quantiles, are not (known to be) mergeable. In this article, 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 which permit approximate multidimensional range counting queries. While most of the results in this article are theoretical in nature, some of the algorithms are actually very simple and even perform better than the previously best known algorithms, which we demonstrate through experiments in a simulated sensor network.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Nov 01, 2013
- Source ID
- 10.1145/2500128
Entities
People
- Graham Cormode
- Jeff M. Phillips
- Ke Yi
- Pankaj Agarwal
- Zengfeng Huang
- Zhewei Wei
Organizations
- Aarhus University
- Army Research Office
- Division of Computing and Communication Foundations
- Duke University
- Engineer Research and Development Center
- National Science Foundation
- Research Grants Council, University Grants Committee
- Tsinghua University
- University of Utah
- University of Warwick