Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows

Vladimir Braverman, Elena Grigorescu, Harry Lang +2

We study the distinct elements and ${\ell }_p$-heavy hitters problems in the sliding window model, where only the most recent $n$ elements in the data stream form the underlying set.…