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

DOI10.1007/978-3-642-25591-5_53MaRDI QIDQ3104649zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

space complexitystreaming algorithm

Mathematics Subject Classification ID

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

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

Cited in

(9)

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

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)