How to Catch L 2-Heavy on Sliding Windows
Vladimir Braverman, Ran Gelles, Rafail Ostrovsky
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 2-heavy elements.
Since the L2 -heavy element problem doesn't satisfy certain conditions, existing methods for sliding windows algorithms, such as smooth histograms or exponetial histograms are not directly applicable toit. In this paper, we develop the first polylogrithmic-memory algorithm for finding L2 elements in the sliding window model.
Our technique allows us not only to find L2-heavy elements, but also heavy elements with respect to L Ρ-with ο < Ρ≤ 2 on sliding windows. By this we completely “close the gap ” and resolve the question of finding L Ρ-heavy elements in the sliding window model with polylogarithmic memory, since it is well known that for Ρ > 2this is impossible.
We demonstrate a broader applicability of our method on two additional examples:We show how to obtain a sliding window approximation of the similarity of two streams, and of the fraction of elements that appear exactly a specified number of times within the window (the a-rarity problem). In these two illustrative examples of our method, we replace the current expected memory bounds with worst case bounds.
comment: Preliminary version appeared in COCOON 2013 pp: 638-650. Full version appeared in Theor. Comput. Sci. 554: 82-94 (2014)
Fetch PDF file of the paper
| Back to Publications List |