How to catch L₂-heavy-hitters on sliding windows
From MaRDI portal
Abstract: Finding heavy-elements (heavy-hitters) in streaming data is one of the central, and well-understood tasks. Despite the importance of this problem, when considering the sliding windows model of streaming (where elements eventually expire) the problem of finding L_2-heavy elements has remained completely open despite multiple papers and considerable success in finding L_1-heavy elements. In this paper, we develop the first poly-logarithmic-memory algorithm for finding L_2-heavy elements in sliding window model. Since L_2 heavy elements play a central role for many fundamental streaming problems (such as frequency moments), we believe our method would be extremely useful for many sliding-windows algorithms and applications. For example, our technique allows us not only to find L_2-heavy elements, but also heavy elements with respect to any L_p for 0<p<2 on sliding windows. Thus, our paper completely resolves the question of finding L_p-heavy elements for sliding windows with poly-logarithmic memory for all values of p since it is well known that for p>2 this task is impossible. Our method may have other applications as well. We demonstrate a broader applicability of our novel yet simple method on two additional examples: we show how to obtain a sliding window approximation of other properties such as the similarity of two streams, or the fraction of elements that appear exactly a specified number of times within the window (the rarity problem). In these two illustrative examples of our method, we replace the current expected memory bounds with worst case bounds.
Recommendations
- How to catch \(L _{2}\)-heavy-hitters on sliding windows
- Nearly optimal distinct elements and heavy hitters on sliding windows
- Finding Heavy Hitters over the Sliding Window of a Weighted Data Stream
- New algorithms for heavy hitters in data streams (invited talk)
- Beating CountSketch for heavy hitters in insertion streams
Cites work
- scientific article; zbMATH DE number 1305436 (Why is no real title available?)
- scientific article; zbMATH DE number 1947403 (Why is no real title available?)
- scientific article; zbMATH DE number 1947405 (Why is no real title available?)
- scientific article; zbMATH DE number 2019620 (Why is no real title available?)
- scientific article; zbMATH DE number 2086663 (Why is no real title available?)
- scientific article; zbMATH DE number 2119719 (Why is no real title available?)
- scientific article; zbMATH DE number 2119721 (Why is no real title available?)
- Data streams. Models and algorithms.
- Data streams: algorithms and applications.
- Database Theory - ICDT 2005
- Finding Heavy Hitters over the Sliding Window of a Weighted Data Stream
- Finding frequent items over sliding windows with constant update time
- LATIN 2004: Theoretical Informatics
- Maintaining time-decaying stream aggregates
- Min-wise independent permutations
- Optimal approximations of the frequency moments of data streams
- Simpler algorithm for estimating frequency moments of data streams
- Size-estimation framework with applications to transitive closure and reachability
- Space lower bounds for distance approximation in the data stream model
- The space complexity of approximating the frequency moments
Cited in
(7)- Succinct summing over sliding windows
- Finding Heavy Hitters over the Sliding Window of a Weighted Data Stream
- Nearly optimal distinct elements and heavy hitters on sliding windows
- How to catch \(L _{2}\)-heavy-hitters on sliding windows
- New algorithms for heavy hitters in data streams (invited talk)
- Symmetric norm estimation and regression on sliding windows
- scientific article; zbMATH DE number 7758337 (Why is no real title available?)
This page was built for publication: How to catch \(L_2\)-heavy-hitters on sliding windows
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744092)
