@article {17617,
	title = {Low discrepancy sets yield approximate min-wise independent permutation families},
	journal = {Information Processing Letters},
	volume = {73},
	year = {2000},
	month = {2000/01/31/},
	pages = {29 - 32},
	abstract = {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,{\textellipsis},n-1} is such a family if for all K⫅{0,1,{\textellipsis},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).},
	keywords = {combinatorial problems, Document filtering, explicit constructions, Information retrieval, Min-wise independent permutations, Pseudorandom permutations},
	isbn = {0020-0190},
	doi = {10.1016/S0020-0190(99)00163-5},
	url = {http://www.sciencedirect.com/science/article/pii/S0020019099001635},
	author = {Saks,Michael and Srinivasan, Aravind and Zhou,Shiyu and Zuckerman,David}
}
