Competitive analysis of maintaining frequent items of a stream

DOI10.1016/j.tcs.2014.09.011zbMath1303.68159OpenAlexW1995654985MaRDI QIDQ476837

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

competitive analysisonline algorithmsdata streamsfrequent items

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27)

Related Items (8)

Online-bounded analysis ⋮ Two-way and one-way quantum and classical automata with advice for online minimization problems ⋮ Quantum versus classical online streaming algorithms with logarithmic size of memory ⋮ Classical and Quantum Computations with Restricted Memory ⋮ Quantum online algorithms with respect to space and advice complexity ⋮ Quantum online streaming algorithms with logarithmic memory ⋮ Online Bounded Analysis ⋮ The fast algorithm for online \(k\)-server problem on trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Streaming techniques and data aggregation in networks of tiny artefacts
• Online algorithms. The state of the art
• Selection and sorting with limited storage
• Finding repeated elements
• The space complexity of approximating the frequency moments
• Who solved the secretary problem
• Data streams. Models and algorithms.
• Competitive Analysis of Maintaining Frequent Items of a Stream
• Encyclopedia of Database Systems
• Competitive Analysis of Aggregate Max in Windowed Streaming
• Random sampling with a reservoir
• Learning from Data Streams
• Probability and Computing

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