How to catch L₂-heavy-hitters on sliding windows
From MaRDI portal
Publication:744092
DOI10.1016/J.TCS.2014.06.008zbMATH Open1360.68899arXiv1012.3130OpenAlexW2096013126MaRDI QIDQ744092FDOQ744092
Authors: Vladimir Braverman, Ran Gelles, Rafail Ostrovsky 
Publication date: 6 October 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1012.3130
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
- The space complexity of approximating the frequency moments
- Data streams. Models and algorithms.
- Optimal approximations of the frequency moments of data streams
- Data streams: algorithms and applications.
- Space lower bounds for distance approximation in the data stream model
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Size-estimation framework with applications to transitive closure and reachability
- Title not available (Why is that?)
- Database Theory - ICDT 2005
- Min-wise independent permutations
- Simpler algorithm for estimating frequency moments of data streams
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Finding Heavy Hitters over the Sliding Window of a Weighted Data Stream
- Maintaining time-decaying stream aggregates
- LATIN 2004: Theoretical Informatics
- Finding frequent items over sliding windows with constant update time
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)
- Title not available (Why is that?)
- Symmetric norm estimation and regression on sliding windows
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)
