Formalization of Randomized Approximation Algorithms for Frequency Moments

Emin Karayel 🌐

April 8, 2022

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

Abstract

In 1999 Alon et. al. introduced the still active research topic of approximating the frequency moments of a data stream using randomized algorithms with minimal space usage. This includes the problem of estimating the cardinality of the stream elements - the zeroth frequency moment. But, also higher-order frequency moments that provide information about the skew of the data stream. (The k-th frequency moment of a data stream is the sum of the k-th powers of the occurrence counts of each element in the stream.) This entry formalizes three randomized algorithms for the approximation of F0, F2 and Fk for k ≥ 3 based on [1, 2] and verifies their expected accuracy, success probability and space usage.
BSD License

Topics

Related Publications

  • Karayel, E. (2022). Formalization of Randomized Approximation Algorithms for Frequency Moments. Schloss Dagstuhl - Leibniz-Zentrum Für Informatik. https://doi.org/10.4230/LIPICS.ITP.2022.21

Theories of Frequency_Moments