Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows

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 Oleft(frac1ε2log nlogfrac1εloglog n+frac1εlog2 nright) bits of space. For ℓp-heavy hitters, we provide an algorithm using space Oleft(frac1εplog3 nleft(loglog n+logfrac1εright)right) for 0<p≤ 2, improving upon the best-known algorithm for ℓ2-heavy hitters (Braverman et al., COCOON 2014), which has space complexity Oleft(frac1ε4log3 nright). We also show lower bounds of Omegaleft(frac1εlog2 n+frac1ε2log nright) for distinct elements and Omegaleft(frac1εplog2 nright) for ℓp-heavy hitters.