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

DOI10.1016/j.tcs.2023.114317OpenAlexW4388906608MaRDI QIDQ6140352

Riku Nitta, Naonori Kakimura

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

• Unnamed Item
• Unnamed Item
• Approximate counting: a detailed analysis
• Finding repeated elements
• The space complexity of approximating the frequency moments
• Mergeable summaries
• A Randomized Algorithm for Finding Frequent Elements in Streams Using O(loglogN) Space
• Counting large numbers of events in small registers
• An Optimal Algorithm for ℓ ₁ -Heavy Hitters in Insertion Streams and Related Problems
• An improved data stream summary: the count-min sketch and its applications
• Algorithms for Big Data
• Database Theory - ICDT 2005

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