Loading...
Please wait, while we are loading the content...
Similar Documents
Testing k-wise independence over streaming data.
| Content Provider | CiteSeerX |
|---|---|
| Author | Chung, Kai-Min Liu, Zhenming Mitzenmacher, Michael |
| Abstract | Following on the work of Indyk and McGregor [5], we consider the problem of identifying correlations in data streams. They consider a model where a stream of pairs (i, j) ∈ [n] 2 arrive, giving a joint distribution (X, Y). They find approximation algorithms for how close the joint distribution is to the product of the marginal distributions under various metrics, which naturally corresponds to how close X and Y are to being independent. We extend their main result to higher dimensions, where a stream of m k-dimensional vectors in [n] k arrive, and we wish to approximate the ℓ2 distance between the joint distribution and the product of the marginal distributions in a single pass. Our analysis gives a randomized algorithm that is a (1±ɛ) approximation (with probability 1 − δ) that requires space logarithmic in n and m and proportional to 3 k. 0 1 |
| File Format | |
| Access Restriction | Open |
| Content Type | Text |