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

DOI10.1016/J.TCS.2023.114317MaRDI QIDQ6140352zbMATH OpenOpenAlexFDO

Authors Naonori Kakimura, Riku Nitta

Publication date 2 January 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2023.114317

zbMATH Keywords

streaming algorithmsfrequent itemsprobabilistic counting

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 1947405 (Why is no real title available?)
• scientific article; zbMATH DE number 2086663 (Why is no real title available?)
• A randomized algorithm for finding frequent elements in streams using \(O(\log \log N)\) space
• Algorithms for Big Data
• An improved data stream summary: the count-min sketch and its applications
• An optimal algorithm for \(\ell_1\)-heavy hitters in insertion streams and related problems
• Approximate counting: a detailed analysis
• Counting large numbers of events in small registers
• Database Theory - ICDT 2005
• Finding repeated elements
• Mergeable summaries
• The space complexity of approximating the frequency moments

This page was built for publication: Randomized counter-based algorithms for frequency estimation over data streams in \(O(\log \log N)\) space

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