Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows

2018/05/01 by Braverman, Vladimir, Grigorescu, Elena, Lang, Harry +2 · 4 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1805.00212

Abstract

We study the distinct elements and ℓ_p-heavy hitters problems in the sliding window model, where only the most recent n elements in the data stream form the underlying set. We first introduce the composable histogram, a simple twist on the exponential (Datar et al., SODA 2002) and smooth histograms (Braverman and Ostrovsky, FOCS 2007) that may be of independent interest. We then show that the composable histogram along with a careful combination of existing techniques to track either the identity or frequency of a few specific items suffices to obtain algorithms for both distinct elements and ℓ_p-heavy hitters that are nearly optimal in both n and ε. Applying our new composable histogram framework, we provide an algorithm that outputs a (1+ε)-approximation to the number of distinct elements in the sliding window model and uses O((1)/(ε²)log nlog\frac1εloglog n+\frac1εlog² n) bits of space. For ℓ_p-heavy hitters, we provide an algorithm using space O((1)/(ε^p)log³ n(loglog n+log\frac1ε)) for 0

Cited by

• Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
• The Expiration Streaming Model: Diameter, k-Center, Counting, Sampling, and Friends
• Unbiased Insights: Optimal Streaming Algorithms for ℓ_p Sampling, the Forget Model, and Beyond
• On Fine-Grained Distinct Element Estimation

Related

• Sliding Windows with Limited Storage
• An exact and O(1) time heaviest and lightest hitters algorithm for\n sliding-window data streams
• Element Distinctness, Frequency Moments, and Sliding Windows
• Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model
• Differentially Private L₂-Heavy Hitters in the Sliding Window Model