How to catch \(L_2\)-heavy-hitters on sliding windows

DOI10.1016/j.tcs.2014.06.008zbMath1360.68899arXiv1012.3130OpenAlexW2096013126MaRDI QIDQ744092

Rafail Ostrovsky, Ran Gelles, Vladimir Braverman

Publication date: 6 October 2014

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

Full work available at URL: https://arxiv.org/abs/1012.3130

zbMATH Keywords

approximation algorithmsdata streamsheavy hitterssliding window model

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Related Items

Symmetric norm estimation and regression on sliding windows, Unnamed Item, Succinct summing over sliding windows

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding frequent items over sliding windows with constant update time
• The space complexity of approximating the frequency moments
• Size-estimation framework with applications to transitive closure and reachability
• Min-wise independent permutations
• Data streams. Models and algorithms.
• Space lower bounds for distance approximation in the data stream model
• Optimal approximations of the frequency moments of data streams
• Simpler algorithm for estimating frequency moments of data streams
• Database Theory - ICDT 2005
• Finding Heavy Hitters over the Sliding Window of a Weighted Data Stream
• Maintaining time-decaying stream aggregates
• LATIN 2004: Theoretical Informatics