Premium
Completeness and robustness properties of min‐wise independent permutations * †
Author(s) -
Broder Andrei Z.,
Mitzenmacher Michael
Publication year - 2001
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/1098-2418(200101)18:1<18::aid-rsa2>3.0.co;2-m
Subject(s) - robustness (evolution) , mathematics , combinatorics , random variable , discrete mathematics , random permutation , permutation (music) , algorithm , statistics , symmetric group , biochemistry , chemistry , physics , acoustics , gene
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. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 18–30, 2001