Min-wise independent permutations (extended abstract)

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

We define and study the notion of min-wise independent families of permutations. We say that F?Sn (the symmetric group) is min-wise independent if for any set X?n and any x?X, when ? is chosen at random in F we havePr(min{?(X)}=?(x))=1|X| . In other words we require that all the elements of any fixed set X have an equal chance to become the minimum element of the image of X under ?. 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.

Subfields: Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Probabilistic & Bayesian Methods

Citations in the corpus

Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, methodology): “Here we list a number of practical scenarios where the MIPS problem is solved as a subroutine: (i) recommender system, (ii) large-scale object detection with DPM, (iii) structural SVM, and (iv) multi-class label prediction.”
AlphaClean: Automatic Generation of Data Cleaning Pipelines (2019, methodology): “replace(thresh, attr) runs the minhash de-duplication algorithm [11] to find similar values and sets them to be equal, and fd.”
RUPEE: A fast and accurate purely geometric protein structure search (2018, methodology): “For this task, min-hashing [29] and 169 locality sensitive hashing (LSH) [30] can be combined to reduce this to subquadratic 170 time.”
Improved Consistent Sampling, Weighted Minhash and L1 Sketching (2010, methodology): “In this paper, we will sometimes refer to the consistent weighted samples (or invertible functions of such samples) as Weighted Minhash, since they generalize the min-wise permutation hashes of [3] from binary to real weights.”
One Permutation Hashing (2012, methodology): “This method is known as minwise hashing (Broder, 1997; Broder et al., 1998; 1997).”
Fast locality-sensitive hashing (2011, methodology): “[8] developed an LSH based on min-wise independent permutations for the Jaccard similarity for sets.”
On the resemblance and containment of documents (1997, background): “(See [4] for an in-depth discussion of this topic.”
A Sketch Algorithm for Estimating Two-Way and Multi-Way Associations (2007, background): “…numerous applications such as association rules (Brin et al. 1997; Brin, Motwani, and Silverstein 1997), clustering (Guha, Rastogi, and Shim 1998; Broder 1998; Aggarwal et al. 1999; Haveliwala, Gionis, and Indyk 2000; Haveliwala et al. 2002), query optimization (Matias, Vitter, and Wang 1998;…”
Asymmetric Minwise Hashing for Indexing Binary Inner Products and Set Containment (2015, methodology): “Minwise hashing (or minhash) [6, 7, 27] is a popular technique deployed by big data industries for these tasks.”
Densifying One Permutation Hashing via Rotation for Fast Near Neighbor Search (2014, methodology): “By an elementary probability argument, This method is known as minwise hashing (Broder, 1997; Broder et al., 1998; 1997).”
Web-Scale Image Clustering Revisited (2015, background): “NEARLY two decades ago [6], discovering duplicates among millions of web documents was the motivation behind one of the first locality sensitive hashing (LSH) schemes, later known as MinHash [7].”