Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model

2025/04/29 by Feng, Shiyuan, Swartworth, William, Woodruff, David P. · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2504.21175

Abstract

We consider the heavy-hitters and F_p moment estimation problems in the sliding window model. For F_p moment estimation with 1

Cited by

• The Expiration Streaming Model: Diameter, k-Center, Counting, Sampling, and Friends
• Optimally detecting uniformly-distributed ℓ₂ heavy hitters in data streams

Related

• Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows
• Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models
• Symmetric Norm Estimation and Regression on Sliding Windows
• Differentially Private L₂-Heavy Hitters in the Sliding Window Model
• An exact and O(1) time heaviest and lightest hitters algorithm for\n sliding-window data streams