Measuring Independence of Datasets

Monday, May 11, 2009 - 5:03pm


MONDAY, MAY 18, 2009
3:30 – 4:30
Computer Science Conference Room, Harold Frank Hall Rm. 1132

HOST: Subhash Suri

Ph.D. Candidate
Computer Science Department, UCLA

Title: Measuring Independence of Datasets


A data stream model represents setting where approximating pairwise, or
$k$-wise, independence with sublinear memory is of considerable
importance. 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 the streaming model. 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.

This talk covers our recent paper “Measuring Independence of Datasets”
(submitted). We solve the main open problem posed by of 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 $(\epsilon, \delta)$-approximation of the
statistical distance between the joint and product distributions defined
by a stream of $k$-tuples. Our algorithm requires $O(\left({1\over
\epsilon}\log({nm\over \delta})\right)^{(30+k)^k})$ memory and a single
pass over the data stream.

Joint work with Rafail Ostrovsky (UCLA).

Bio: Vladimir Braverman is a Ph.D. candidate at UCLA; his advisor is Rafail Ostrovsky. His main interests are algorithms for data streams, communication complexity and related areas. He received his B.Sc. and M.Sc. degrees from Ben-Gurion University Israel, wherehis advisor was Daniel Berend. Prior to attending UCLA, he led a research team at HyperRoll, working with Yossi Matias.