%0 Journal Article
%J Information Processing Letters
%D 2000
%T Low discrepancy sets yield approximate min-wise independent permutation families
%A Saks,Michael
%A Srinivasan, Aravind
%A Zhou,Shiyu
%A Zuckerman,David
%K combinatorial problems
%K Document filtering
%K explicit constructions
%K Information retrieval
%K Min-wise independent permutations
%K Pseudorandom permutations
%X Motivated by a problem of filtering near-duplicate Web documents, Broder, Charikar, Frieze and 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⫅{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 nO(logn) for ϵ=1/nΘ(1), 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|≤2O(log2/3n), with ϵ≥2−O(log2/3n).
%B Information Processing Letters
%V 73
%P 29 - 32
%8 2000/01/31/
%@ 0020-0190
%G eng
%U http://www.sciencedirect.com/science/article/pii/S0020019099001635
%N 1–2
%R 10.1016/S0020-0190(99)00163-5