Distributed Statistical Estimation of Matrix Products with Applications
Distributed Statistical Estimation of Matrix Products with Applications
复制标题
DOI：
10.1145/3196959.3196964
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
David P. Woodruff;Qin Zhang
中科院分区：
文献类型：
--
作者：
David P. Woodruff;Qin Zhang
我们考虑在分布式环境中对整数上的矩阵产品的统计估计，在那里我们有两个当事方的爱丽丝和鲍勃，而爱丽丝则持有矩阵A，而鲍勃则持有矩阵B。 。沟通的回合。一对带有最大交叉点的集合。以及随机均匀地采样一对相交对组的问题。
We consider statistical estimations of a matrix product over the integers in a distributed setting, where we have two parties Alice and Bob; Alice holds a matrix A and Bob holds a matrix B, and they want to estimate statistics of $A \cdot B$. We focus on the well-studied $\ell_p$-norm, distinct elements ($p = 0$), $\ell_0$-sampling, and heavy hitter problems. The goal is to minimize both the communication cost and the number of rounds of communication. This problem is closely related to the fundamental set-intersection join problem in databases: when $p = 0$ the problem corresponds to the size of the set-intersection join. When $p = ınfty$ the output is simply the pair of sets with the maximum intersection size. When $p = 1$ the problem corresponds to the size of the corresponding natural join. We also consider the heavy hitters problem which corresponds to finding the pairs of sets with intersection size above a certain threshold, and the problem of sampling an intersecting pair of sets uniformly at random.