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

DOI10.1016/J.TCS.2023.114317OpenAlexW4388906608MaRDI QIDQ6140352FDOQ6140352

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

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

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)