A randomized algorithm for finding frequent elements in streams using O( N) space

DOI10.1007/978-3-642-25591-5_53zbMATH Open1350.68286OpenAlexW1522705574MaRDI QIDQ3104649FDOQ3104649

Authors: Masatora Ogata, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita 

Publication date: 16 December 2011

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-25591-5_53

Recommendations

• On Finding Frequent Elements in a Data Stream
• Finding Frequent Elements in Non-bursty Streams
• The space complexity of approximating the frequency moments
• Competitive Analysis of Maintaining Frequent Items of a Stream
• scientific article; zbMATH DE number 1256715

zbMATH Keywords

streaming algorithmspace complexity

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20)

Cited In (9)

• Randomized counter-based algorithms for frequency estimation over data streams in \(O(\log \log N)\) space
• A parallel space saving algorithm for frequent items and the Hurwitz zeta distribution
• Finding a Duplicate and a Missing Item in a Stream
• Finding duplicates in a data stream
• A cumulative not-first/not-last filtering algorithm in \(O(n^2 \log(n))\)
• Finding Frequent Elements in Non-bursty Streams
• Competitive analysis of maintaining frequent items of a stream
• On space and time complexity of loosely-stabilizing leader election
• On Finding Frequent Elements in a Data Stream

This page was built for publication: A randomized algorithm for finding frequent elements in streams using \(O(\log \log N)\) space

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