Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families

摘要

Motivated by a problem of filtering near-duplicate Web documents, Broder, Charikar, Frieze & Mitzenmacher defined the following notion of ε-approximate min-wise independent permutation families. A multiset F of permutations of {0, 1, ... , n - 1} is such a family if for all K is contained in {0, 1, ... , n - 1} and any x ∈ K, a permutation π chosen uniformly at random from F satisfies | Pr[min{π(K)} = π(x)] - 1/(|K|) ≤ε/(|K|). We show connections of such families with low discrepancy sets for geometric rectangles, and give explicit constructions of such families F of size n~(O(log n)~(1/2)) for ε = 1/n~Θ, improving upon the previously best-known bound of Indyk. We also present polynomial-size constructions when the min-wise condition is required only for |K| ≤ 2~(O(log~(2/3)n), with ε≥ 2~(-O(log~(2/3)n)).