High frequency moments via max-stability

Alexandr AndoniICASSP 2017 · OpenReview

Abstract

We present anew, simple algorithm for sketching the k > 2 frequency moment of a dynamic stream, or simply the ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> norm of a vector in the linear sketching model. The new algorithms are based on exponentially distributed random variables, which possess a certain “max-stability” property, similar in spirit to the “p-stability” property used in [Indyk, JACM'06] for sketching ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> norms for k ≤ 2. Our resulting sketching algorithm can be seen as a “weak embedding” of an n-dimensional ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> space into 1 <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</sub> space of dimension m = O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1-2/k</sup> log n): it preserves the norm of a vector up to constant approximation, with constant probability. We note that this dimension is optimal for linear embeddings (sketches) with constant approximation, as shown in [Andoni-Nguyen-Polyanskiy-Wu, ICALP'13]. The preliminary version of this result has appeared as a blog post in 2012, and its main idea has since been used in other streaming algorithms.
BibTeX
@inproceedings{andoni2017high,
  author = {Alexandr Andoni},
  title = {{High frequency moments via max-stability}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2017},
  url = {https://openreview.net/forum?id=HoZNzjXn8ii},
}

Loading related content...

Figure