Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families
Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families
复制标题
低差异集产生近似最小独立排列族
DOI：
10.1007/978-3-540-48413-4_2
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
David Zuckerman
中科院分区：
文献类型：
--
作者：
M. Saks;A. Srinivasan;Shiyu Zhou;David Zuckerman
受过滤近似重复Web文档的问题的启发，Broder，Charikar，Frieze和Mitzenmacher定义了以下e-近似最小独立置换族的概念[2]。一个{0，1，.}的排列的多集合\（\mathcal{F}\）。，n-1}是这样的族，如果对所有K ∈ {0，1，...，n-1}且任意x ∈ K，随机一致选取的置换π形成\（\mathcal{F}\）
Motivated by a problem of filtering near-duplicate Web documents, Broder, Charikar, Frieze & Mitzenmacher defined the following notion of e-approximate min-wise independent permutation families [2]. A multiset \(\mathcal{F}\) of permutations of {0,1, ... , n–1} is such a family if for all K ⊆ {0,1, ..., n–1} and any x ∈ K, a permutation π chosen uniformly at random form \(\mathcal{F}\) statisfies