Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows.

DOI10.4230/LIPIcs.APPROX-RANDOM.2018.7OpenAlexW2964311170MaRDI QIDQ5009499

Samson Zhou, David P. Woodruff, Vladimir Braverman, Elena Grigorescu, Harry Lang

Publication date: 4 August 2021

Full work available at URL: https://arxiv.org/abs/1805.00212

zbMATH Keywords

streaming algorithmsheavy hitterssliding windowsdistinct elements

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (2)

Symmetric norm estimation and regression on sliding windows ⋮ Improved Algorithms for Time Decay Streams

Uses Software

• HyperLogLog

Cites Work

• Distributed streams algorithms for sliding windows
• Computing diameter in the streaming and sliding-window models
• Finding frequent items in data streams
• Dynamic Graphs in the Sliding-Window Model
• Optimal approximations of the frequency moments of data streams
• An improved data stream summary: the count-min sketch and its applications
• Maintaining Stream Statistics over Sliding Windows
• An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
• Zero-One Laws for Sliding Windows and Universal Sketches
• Finding Heavy Hitters over the Sliding Window of a Weighted Data Stream
• Algorithms - ESA 2003
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows.