Deterministic Heavy Hitters with Sublinear Query Time

DOI10.4230/LIPIcs.APPROX-RANDOM.2018.18OpenAlexW2963650209MaRDI QIDQ5009510

Vasileios Nakos, Yi Li

Publication date: 4 August 2021

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

zbMATH Keywords

heavy hitterssketching algorithmturnstile modelstrongly explicit

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Approximate Sparse Recovery: Optimizing Time and Measurements
• Compressed sensing and best 𝑘-term approximation
• Sparser Johnson-Lindenstrauss Transforms
• Lower Bounds on Frequency Estimation of Data Streams (Extended Abstract)
• An improved data stream summary: the count-min sketch and its applications
• For-All Sparse Recovery in Near-Optimal Time
• The Data Stream Space Complexity of Cascaded Norms
• Turnstile streaming algorithms might as well be linear sketches
• Database Theory - ICDT 2005
• Streaming Algorithms via Precision Sampling

This page was built for publication: Deterministic Heavy Hitters with Sublinear Query Time