**
Measuring Independence of Datasets.
**

*
Vladimir Braverman, Rafail Ostrovsky
*

**
Abstract:
**

Approximating pairwise, or k-wise, independence with sublinear memory is of considerable importance in the data stream model. In the streaming model the joint distribution is given by a stream of k-tuples, with the goal of testing correlations among the components measured over the entire stream. Indyk and McGregor (SODA 08) recently gave exciting new results for measuring pairwise independence in this model.

*Statistical distance* is one of the most fundamental metrics for
measuring the similarity of two distributions, and it has been a metric of
choice in many papers that discuss distribution closeness.
For pairwise independence, the Indyk and McGregor methods provide log n-approximation under
statistical
distance between the joint and product distributions in the streaming model.
Indyk and McGregor leave, as
their main open question, the problem of improving their log
n-approximation for the statistical distance metric.

In this paper we solve the main open problem posed by Indyk and McGregor
for the statistical distance for pairwise independence and extend this result to any constant k. In particular, we present
an algorithm that computes
an( ∊δ )-approximation
of the *statistical distance* between the joint and product distributions defined by a stream of k-tuples.
Our algorithm requires O((1/∊log(nm /^{ } δ))^{(30+k)} ^{k}, memory and a single pass over the data stream.

**comment:**
STOC 2010

Fetch PostScript file of the paper Fetch PDF file of the paper

Back to Publications List |