Declaring independence via the sketching of sketches
Declaring independence via the sketching of sketches
复制标题
通过草图的绘制来宣告独立
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
A. Mcgregor
中科院分区：
文献类型：
--
作者：
P. Indyk;A. Mcgregor
我们认为，在数据流中识别相关性的问题。令人惊讶的是，我们的工作似乎是第一个考虑这个自然问题的。在集中式模型中，我们考虑一个对（i，j）∈ [n]2的流，其频率定义了一个联合分布（X，Y）。在分布式模型中，该对的每个坐标可以单独出现在流中。我们提出了一系列算法来近似X和Y独立的程度，即，联合分布与边际分布的乘积有多接近我们考虑了各种度量的接近度，包括x1，x2，以及X和Y之间的互信息。我们的算法是基于“素描草图”，即，组成小空间线性分布概要。也许具有讽刺意味的是，出现的最大技术挑战与确保我们估计的不同组成部分足够独立有关。
We consider the problem of identifying correlations in data streams. Surprisingly, our work seems to be the first to consider this natural problem. In the centralized model, we consider a stream of pairs (i,j) ∈ [n]2 whose frequencies define a joint distribution (X,Y). In the distributed model, each coordinate of the pair may appear separately in the stream. We present a range of algorithms for approximating to what extent X and Y are independent, i.e., how close the joint distribution is to the product of the marginals. We consider various measures of closeness including ℓ1, ℓ2, and the mutual information between X and Y. Our algorithms are based on "sketching sketches", i.e., composing small-space linear synopses of the distributions. Perhaps ironically, the biggest technical challenges that arise relate to ensuring that different components of our estimates are sufficiently independent.