MinHash and LSH

The Go source tree has 3093 files, not counting tests and very small ones. Pairs of them: 4,781,778. Which files are nearly identical? Comparing every pair honestly is millions of intersections of sets of a thousand elements. Below, the same is done in fewer than two thousand comparisons. Each file is a point on a circle, in order of path; a chord joins a pair the algorithm found suspicious. The colour is how similar the files really are.

With 12 bands of 4 rows there are 1848 suspicious pairs, four hundredths of a per cent of them all. Among them are 1384 of the 1537 pairs that coincide at least by half. Short chords at the edge are families of files in one directory: syscall and the vendored x/sys/unix keep a file for each “system, processor” pair, and these files are produced by generators. Long chords are copies across the whole tree. Go’s type checker lives twice: in go/types for tools and in cmd/compile/internal/types2 for the compiler, and 39 files of the first begin with the words “Code generated… Source: ../../cmd/compile/internal/types2”. And cmd/gofmt/internal.go and go/format/internal.go coincide at 0.994, and both say: these files are identical except for the comment and the package name; do not change one without the other.

The idea

The similarity of two documents is measured by shingles, pieces of several consecutive tokens, like tiles on a roof. Here a shingle is five consecutive Go tokens, with comments thrown out. Jaccard similarity is the share of common shingles among all: J(A, B) = |A ∩ B| / |A ∪ B|. How this came about, and what essays about an oak have to do with it, is in the course chapter “A needle in a haystack”. Here the question is different: how to find similar pairs when there are millions of pairs.

Two steps. MinHash compresses each set of shingles into a signature of K numbers: the i-th number is the smallest hash of the document’s shingles under the i-th hash function. For two documents the i-th numbers coincide with probability exactly equal to J, and the share of matching positions estimates similarity without the sets themselves. LSH cuts the signature into b bands of r numbers and lays documents out in buckets by each band. A pair becomes a candidate if at least one of its bands matches entirely. Similar documents will almost certainly meet, dissimilar ones almost never, and only candidates need an exact check.

Why the minimum

Check this by hand on two real files. bytes/reader.go and strings/reader.go are readers from a byte slice and from a string, written on one pattern. The first has 601 shingles, the second 578, with 495 in common, and J = 495/684 ≈ 0.724. Each permutation picks the first shingle of the union; if it is a common one, that is a “match of minima”.

One permutation is the toss of a coin that comes up “common” with probability J. K permutations give a share of matches with standard deviation √(J(1 − J)/K): with K = 48 and J = 0.72 that is 0.065. The listing below gets an estimate of 0.792 for this pair, one deviation above the truth, and for bytes/iter.go and strings/iter.go 0.562 against a true 0.648. The precision is enough to tell nearly identical from different, not to measure similarity to hundredths. Nobody actually makes permutations, of course: instead of K permutations one takes K hash functions, here the same mixing function with K different seeds.

A signature of 48 numbers replaces a file of 2255 shingles on average. One can keep not the whole number but a few of its low bits: they preserve the match of minima, and a chance match of bits adds 2^−w to the estimate for w bits. The scene above keeps 16 bits each, a correction of less than two hundred-thousandths. This trick is the b-bit MinHash of Ping Li and Arnd Christian König, 2010; they kept even a single bit, paying with a longer signature.

Bands and the S-curve

The signatures cut each comparison down to 48 numbers, but there are still 4.8 million pairs. The second step removes the pairs themselves. Cut the signature into b bands of r numbers. For each band lay the documents out in buckets: documents with the same band go into one bucket. Candidates are the pairs that ended up together in at least one bucket.

The probability is easy to compute. Let the similarity of a pair be s. One band matches entirely with probability s^r, as all r minima must match. It fails to match with 1 − s^r, and none of the b bands match with (1 − s^r)^b. So a pair becomes a candidate with probability

$$P(s) = 1 - \left(1 - s^{r}\right)^{b}.$$

This is an S-shaped curve: almost zero for small s, almost one for large ones, and a steep rise near the threshold s ≈ (1/b)^1/r. The longer the band, the further right the threshold; the more bands, the further left. With 12 bands of 4 rows a pair of similarity 0.8 becomes a candidate with probability 0.998, and a pair of similarity 0.2 with probability 0.019. The dots on the chart are real pairs of Go files: you can see the curve honestly predicts the share found.

A band of one row is useless: two Go files almost always share some common shingle like if err != nil {, and 48 tries to match at least once give 388 thousand candidates. Long bands cut out noise but lose pairs near the threshold: at 4 × 12 only almost exact copies remain. The choice is made so that the threshold stands a little below the similarity needed: a lost pair cannot be brought back, while an extra candidate is weeded out by the exact check. Here 16 × 3 finds 99% of the pairs from 0.5 at the price of 3133 checks, one and a half thousand times fewer than all pairs.

When an exact answer is needed

LSH sometimes loses pairs; that is the price of speed. If losing is not allowed, there is an exact way for the same question, “all pairs with similarity at least t”, and it rests on two simple inequalities.

Size. J(A, B) ≤ min(|A|, |B|) / max(|A|, |B|): there are no more common shingles than in the smaller set, and no fewer in the union than in the larger. Pairs where one set is twice the size of the other will not reach 0.5, and need not even be opened. The listing below uses this filter when it computes all pairs for checking.

Prefix. Order all shingles by one common order, most conveniently from rare to frequent, and write each set in that order. If J(A, B) ≥ t, then A and B have at least ⌈t·|A|⌉ common elements. Then among the first |A| − ⌈t·|A|⌉ + 1 elements of A there is at least one common one: otherwise all the common ones would fit into the remaining ⌈t·|A|⌉ − 1 places. The same holds for B, and the common element that comes earliest lies in the prefixes of both. So it is enough to build an inverted index over the prefixes only and take as candidates the pairs whose prefixes intersect. Rare elements at the start make the index lists short. This is the prefix filter of Surajit Chaudhuri, Venkatesh Ganti and Raghav Kaushik, 2006; Roberto Bayardo, Yiming Ma and Ramakrishnan Srikant showed in 2007 how to enumerate all pairs in large collections with it. Try it in the problem about similar passwords.

The exact way is good while the sets are short or the threshold high. On long documents with a threshold of 0.5 the prefix is half the set, and the gain melts away; then MinHash remains.

Code

The listing does the same on six directories, bytes, strings, both versions of math/rand, go/types and types2: shingles, signatures of 48 minima, LSH 12 × 4, and for comparison an honest search of all pairs with the size filter. The files are read straight from the Go sources that sit in the sandbox together with the compiler.

Of 9591 pairs, 59 became candidates, and these are exactly all 59 pairs of similarity 0.5 and up. In Python the signature is computed by numpy: 48 hash functions over all the shingles of a file at once is one operation on a matrix. In Go the same is two nested loops. The hash functions are splitmix64 mixing with different seeds; before that a shingle is folded into 32 bits by CRC-32.

What it costs

The signatures are O(K·S), where S is the total number of shingles in all documents: the Go tree has almost seven million, and this is the most expensive part. The buckets are O(n·b) with a hash table for each band. Candidates: however many there are, on average P(s) for each pair of similarity s, and with well-chosen b and r only slightly more than the number of real pairs. The check is the exact similarity for each candidate. Memory is K numbers per document, 16 bits each in the scene: 96 bytes instead of 23 KB of source on average.

Where it breaks. Jaccard similarity over shingles sees coincidence of text, not of meaning: rename all the variables, and the shingles become different. Huge buckets drive the number of candidates up quadratically: files made of nothing but boilerplate lines have the same band, and a bucket of a thousand files is half a million pairs. So empty and almost empty documents, such as doc.go files of nothing but comments, are best removed in advance: their signatures coincide by chance.

Where it works

Search engines. Andrei Broder and colleagues in 1997 clustered the pages collected by the AltaVista crawler this way: shingles, similarity and a sample of minima. Gurmeet Manku, Arvind Jain and Anish Das Sarma described in 2007 how Google weeds out nearly identical pages when crawling the web with another fingerprint of the same kind, Moses Charikar’s SimHash, where closeness is measured by the number of differing bits.

Data. Apache Spark has had MinHashLSH since version 2.1: signatures and bands over a table column. Large text collections, including those for training language models, are cleaned of nearly identical documents with MinHash and LSH: otherwise the same text copied to a thousand sites weighs a thousand times as much.

Code and texts. Finding clones in code, borrowings in student work, similar listings and products in a catalogue: wherever “almost the same thing” has to be found among many thousands.

History

The measure of similarity of sets was introduced by the botanist Paul Jaccard in 1901. Andrei Broder in 1997 proposed comparing documents through the minima of the hashes of their shingles, and with Steven Glassman, Mark Manasse and Geoffrey Zweig applied it to everything the AltaVista crawler had collected. In 1998 Broder, Moses Charikar, Alan Frieze and Michael Mitzenmacher analysed which families of permutations will do for this. At the same time Piotr Indyk and Rajeev Motwani proposed locality-sensitive hashing, LSH, for nearest neighbour search. Splitting the signature into bands and the S-curve are treated in detail in the textbook by Anand Rajaraman and Jeffrey Ullman, “Mining of Massive Datasets”.

Problems