A Characterization of Min-Wise Independent Permutations Families (Models of Computation and Algorithms)
Yoshinori Takei, Toshiya Itoh · Institutional Repositories DataBase (IRDB) · 1999
A ${\rm Min}$ -Wise Independent Permutation Family is an efficient tool to estimate similarity of docu- ments.We present a characterization of Exact MWIPFs by size uniformity, which represents certain symmetry of the string representation of a family.Also, we present a general construction strategy which produce any Exact MWIPF using this characterization.