Fourier Transform-based Estimators for Data Sketches

In this paper we consider the problem of estimating the f-moment (∑v∈ [n] (f(x(v))-f(0))) of a dynamic vector x∈ Gⁿ over some abelian group (G,+), where the \|f\|_∞ norm is bounded. We propose a simple sketch and new estimation framework based on the Fourier transform of f. I.e., we decompose f into a linear combination of homomorphisms f₁,f₂,… from (G,+) to (C,×), estimate the fₖ-moment for each fₖ, and synthesize them to obtain an estimate of the f-moment. Our estimators are asymptotically unbiased and have variance asymptotic to \|x\|₀² (\|f\|_∞² m⁻¹ + \|f̂\|₁² m⁻²), where the size of the sketch is O(mlog nlog|G|) bits. When G=Z this problem can also be solved using off-the-shelf ₀-samplers with space O(mlog² n) bits, which does not obviously generalize to finite groups. As a concrete benchmark, we extend Ganguly, Garofalakis, and Rastogi's singleton-detector-based sampler to work over G using O(mlog nlog|G|log(mlog n)) bits. We give some experimental evidence that the Fourier-based estimation framework is significantly more accurate than sampling-based approaches at the same memory footprint.