Beating CountSketch for heavy hitters in insertion streams

DOI10.1145/2897518.2897558zbMath1373.68190arXiv1511.00661OpenAlexW1956340982MaRDI QIDQ5361876

Nikita Ivkin, Vladimir Braverman, David P. Woodruff, Stephen R. Chestnut

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.00661

zbMATH Keywords

chainingdata streamsheavy hitters

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Related Items (7)

Three‐wise independent random walks can be slightly unbounded ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Forty years of frequent items ⋮ Tracking the l_2 Norm with Constant Update Time ⋮ Continuous Monitoring of l_p Norms in Data Streams ⋮ Perfect $L_p$ Sampling in a Data Stream

This page was built for publication: Beating CountSketch for heavy hitters in insertion streams