Measuring $k$-Wise Independence of Streaming Data

摘要: In their seminal work, Alon, Matias, and Szegedy introduced several sketching techniques, including showing that 4-wise independence is sufficient to obtain good approximations of the second frequency moment. this we show technique can be extended product domains $[n]^k$ by using independent functions on $[n]$. Our work extends Indyk McGregor, who showed result for $k = 2$. Their primary motivation was problem identifying correlations in data streams. model, a stream pairs $(i,j) \in [n]^2$ arrive, giving joint distribution $(X,Y)$, they find approximation algorithms how close marginal distributions under various metrics, which naturally corresponds $X$ $Y$ are being independent. By our technique, new approximating $\ell_2$ distance between $k$-ary vectors, instead just pairs, single pass. analysis gives randomized algorithm $(1 \pm \epsilon)$ (with probability $1-\delta$) requires space logarithmic $n$ $m$ proportional $3^k$.