2026-07-23T22:06:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4721 2024-03-06T10:35:18Z ddc:004 open_access

An Optimal Algorithm for Large Frequency Moments Using O(n^(1-2/k)) Bits Braverman, Vladimir Katzman, Jonathan Seidell, Charles Vorsanger, Gregory Streaming Algorithms Randomized Algorithms Frequency Moments Heavy Hitters In this paper, we provide the first optimal algorithm for the remaining open question from the seminal paper of Alon, Matias, and Szegedy: approximating large frequency moments. We give an upper bound on the space required to find a k-th frequency moment of O(n^(1-2/k)) bits that matches, up to a constant factor, the lower bound of Woodruff et. al for constant epsilon and constant k. Our algorithm makes a single pass over the stream and works for any constant k > 3. It is based upon two major technical accomplishments: first, we provide an optimal algorithm for finding the heavy elements in a stream; and second, we provide a technique using Martingale Sketches which gives an optimal reduction of the large frequency moment problem to the all heavy elements problem. We also provide a polylogarithmic improvement for frequency moments, frequency based functions, spatial data streams, and measuring independence of data sets. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vladimir Braverman and Jonathan Katzman and Charles Seidell and Gregory Vorsanger 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.531 urn:nbn:de:0030-drops-47217 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.531 eng https://creativecommons.org/licenses/by/3.0/legalcode