Min-Wise Independent Permutations | Awesome Learning to Hash Add your paper to Learning2Hash

Min-Wise Independent Permutations

Andrei Z Broder,Moses Charikar,Alan M Frieze,Michael Mitzenmacher. JCSS 1998


We define and study the notion of min-wise independent families of permutations. Our research was motivated by the fact that such a family (under some relaxations) is essential to the algorithm used in practice by the AltaVista web index software to detect and filter near-duplicate documents. However, in the course of our investigation we have discovered interesting and challenging theoretical questions related to this concept we present the solutions to some of them and we list the rest as open problems.