Hierarchical Sampling from Sketches: Estimating Functions over Data Streams

摘要

We present a randomized procedure named Hierarchical Sampling from Sketches (Hss) that can be used for estimating a class of functions over the frequency vector f of update streams of the form varPsi(S)=å_i=1ny(|f_i|)varPsi(mathcal {S})=sum_{i=1}^{n}psi(vert {f_{i}}vert ) . We illustrate this by applying the Hss technique to design nearly space-optimal algorithms for estimating the pth moment of the frequency vector, for real p≥2 and for estimating the entropy of a data stream.