High frequency moments via max-stability
Alexandr Andoni · 2017
We present anew, simple algorithm for sketching the k > 2 frequency moment of a dynamic stream, or simply the ℓknorm 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 ℓknorms for k ≤ 2. Our resulting sketching algorithm can be seen as a “weak embedding” of an n-dimensional ℓkspace into 1∞space of dimension m = O(n1-2/klog 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.