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

Related Items (3)

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

This page was built for publication: How to catch \(L_2\)-heavy-hitters on sliding windows