Completeness and robustness properties of min-wise independent permutations
Completeness and robustness properties of min-wise independent permutations
复制标题
最小独立排列的完整性和鲁棒性
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
M. Mitzenmacher
中科院分区：
文献类型：
--
作者：
A. Broder;M. Mitzenmacher
我们提供了几个新的结果有关的概念，最小明智的独立性。我们的主要结果是，任何随机抽样计划的相对交集的基础上测试平等的样本产生一个等价的min-wise独立的家庭。因此，在某种意义上，对于这种类型的估计，最小独立族是完备的。我们还讨论了鲁棒性的概念，这是一个扩展最小独立性的概念，可以在实践中更有效地使用它。从我们对鲁棒性的考虑中产生的一个令人惊讶的结果是，在来自最小独立族的随机置换下，固定集合的任何元素都有同等的机会获得集合的图像中的任何秩，而不仅仅是定义所要求的最小值。
We provide several new results related to the concept of min-wise independence. Our main result is that any randomized sampling scheme for the relative intersection of sets based on testing equality of samples yields an equivalent min-wise independent family. Thus, in a certain sense, min-wise independent families are complete for this type of estimation. We also discuss the notion of robustness, a concept extending min-wise independence to allow more efficient use of it in practice. A surprising result arising from our consideration of robustness is that under a random permutation from a min-wise independent family, any element of a fixed set has an equal chance to get any rank in the image of the set, not only the minimum as required by definition.