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

streaming algorithmspace complexity

Mathematics Subject Classification ID

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

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)

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

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)