An Optimal Algorithm for ℓ 1 -Heavy Hitters in Insertion Streams and Related Problems

DOI10.1145/3264427zbMath1454.68190arXiv1603.00213OpenAlexW2898069179MaRDI QIDQ4629972

David P. Woodruff, Arnab Bhattacharyya, Palash Dey

Publication date: 28 March 2019

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

votingwinner determinationstreaming algorithmsheavy hitters

Mathematics Subject Classification ID

Voting theory (91B12) Online algorithms; streaming algorithms (68W27)

Related Items (1)

Randomized counter-based algorithms for frequency estimation over data streams in \(O(\log \log N)\) space

This page was built for publication: An Optimal Algorithm for ℓ ₁ -Heavy Hitters in Insertion Streams and Related Problems