Sketching, Moment Estimation, and the Lévy-Khintchine Representation Theorem
This paper introduces a generic sketching scheme for estimating -moments in the turnstile streaming model by hashing indices to Lévy processes, leveraging the Lévy-Khintchine representation theorem to unify existing methods and characterize the tractability of a broad class of functions, including nearly periodic and heterogeneous cases.