Competitive analysis of maintaining frequent items of a stream

DOI10.1016/J.TCS.2014.09.011MaRDI QIDQ476837zbMATH OpenOpenAlexFDO

Authors Yiannis Giannakopoulos, Elias Koutsoupias

Publication date 2 December 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.09.011

zbMATH Keywords

online algorithmscompetitive analysisdata streamsfrequent items

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27)

Recommendations

• Competitive Analysis of Maintaining Frequent Items of a Stream
• The frequent items problem in online streaming under various performance measures
• The Frequent Items Problem in Online Streaming Under Various Performance Measures
• On Finding Frequent Elements in a Data Stream
• A randomized algorithm for finding frequent elements in streams using \(O(\log \log N)\) space

Cites work

• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 2119721 (Why is no real title available?)
• Competitive Analysis of Aggregate Max in Windowed Streaming
• Competitive Analysis of Maintaining Frequent Items of a Stream
• Data streams. Models and algorithms.
• Data streams: algorithms and applications.
• Encyclopedia of Database Systems
• Finding repeated elements
• Learning from Data Streams
• Online algorithms. The state of the art
• Probability and Computing
• Random sampling with a reservoir
• Selection and sorting with limited storage
• Streaming techniques and data aggregation in networks of tiny artefacts
• The space complexity of approximating the frequency moments
• Who solved the secretary problem

Cited in

(10)

• Quantum online streaming algorithms with logarithmic memory
• Classical and Quantum Computations with Restricted Memory
• Competitive Analysis of Maintaining Frequent Items of a Stream
• Online-bounded analysis
• The frequent items problem in online streaming under various performance measures
• Online bounded analysis
• Quantum versus classical online streaming algorithms with logarithmic size of memory
• Quantum online algorithms with respect to space and advice complexity
• The fast algorithm for online \(k\)-server problem on trees
• Two-way and one-way quantum and classical automata with advice for online minimization problems

This page was built for publication: Competitive analysis of maintaining frequent items of a stream

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