Mergeable summaries

DOI10.1145/2500128MaRDI QIDQ2943556zbMATH OpenOpenAlexFDO

Authors Graham Cormode, Zengfeng Huang, Jeff M. Phillips, Zhewei Wei, Ke Yi, Pankaj K. Agarwal

Publication date 3 September 2015

Published in ACM Transactions on Database Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2500128

zbMATH Keywords

quantilesheavy hittersdata summarization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Nonnumerical algorithms (68W05) Database theory (68P15)

Recommendations

• Summary data structures for massive data
• An improved data stream summary: the count-min sketch and its applications
• LATIN 2004: Theoretical Informatics
• Distributed streams algorithms for sliding windows
• A randomized online quantile summary in \(O(\frac 1\varepsilon\log\frac 1\varepsilon)\) words

Cited in

(16)

• Give me some slack: efficient network measurements
• Randomized counter-based algorithms for frequency estimation over data streams in O( N) space
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
• Intermediate value linearizability: a quantitative correctness criterion
• Relative error streaming quantiles
• Frequent directions: simple and deterministic matrix sketching
• Extensible query optimizers in practice
• Give me some slack: efficient network measurements
• The Communication Complexity of Distributed epsilon-Approximations
• Asymptotics of wide remedians
• CONQUEST: A coarse-grained algorithm for constructing summaries of distributed discrete datasets
• Communication-efficient distributed covariance sketch, with application to distributed PCA
• Indexing for summary queries, theory and practice
• Intermediate value linearizability: a quantitative correctness criterion
• Randomized algorithms for tracking distributed count, frequencies, and ranks
• Summary data structures for massive data

This page was built for publication: Mergeable summaries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2943556)