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

Awesome Learning to Hash

A webpage dedicated to the latest research on learning-to-hash, including state-of-the-art deep hashing models, all updated on a weekly basis. Maintained by Sean Moran.

Contact Sean Moran about this survey or website. Made with Jekyll and Hyde.

Min-Wise Independent Permutations

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

[PDF]    
JCSS

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.

Similar Work