Motivation and About This Document

This article gives an overview of dimensionality reduction and finding similar elements in large datasets using shingling, feature hashing, MinHashing, and Locality Sensitive Hashing (LSH) from an engineering perspective. Many of the documents we’ve come across either go into depth on the theory or describe an application in detail; however, few tie together the theory and the implementation details. In this article, we lean towards a practical implementation and parameter tuning perspective while referencing the papers and publications which lay the theoretical foundation.

The collection of algorithms described in this article can be used to find similar documents among a corpus of documents in O(n) time. Documents, in this case, are broadly defined — the documents could be email, source code, tweets, images, html — the possibilities are limitless. In fact, there are a multitude of applications of these algorithms and they can be tuned to produce specific results. For instance, the parameters to this process can be calibrated to provide near exact matching of documents for singling out near duplicates in large datasets (with a similarity threshold = 0.9, 0.95, 0.99). Furthermore, while a lower similarity (threshold = 0.5, 0.6, 0.7) can be used to detect document containment (a large portion of a document appears within another document), source code version differences and plagiarism. These applications are meant to give the reader a foundation for their applicability but the potential usages are vast.

The document is organized in the following manner:

• Part 1 — A general overview of the terms used in the document. Additionally, we show an example of computing document similarity using Shingling, MinHash, Locality Sensitive Hashing.
• Part 2 — The technical details of each part of the algorithm. We cover universal hash functions, djb2a hash function, Shingling, MinHash, and Locality Sensitive Hashing and how they tie into the big picture.
• Part 3 — We provide a fully worked example of computing document similarity among sample web pages. Additionally, we provide links to further reading and supply all of the project files discussed in this documents.

Notes on the Scala implementation

The implementation chosen is purely function Scala. As a result, all of the code is side effect free and uses immutable data structures. A few notes on the code:

1. We only use val variables, which are immutable.
2. The :+ operator adds an item to an immutable data structure by creating a new structure with the appended data. A mnemonic to remember the operator is the colon goes on the collection side.
3. We implement a lot of functionality using tail recursion. The Scala compiler will optimize these effectively to while loops. Each tail recursive call uses the same stack frame.
4. The .zipped call takes two sequential iterable sequences and zips them together.

scala> val a = Vector(1,2,3) a: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3) scala> val b = Vector(4,5,6) b: scala.collection.immutable.Vector[Int] = Vector(4, 5, 6) scala> val zipped = (a,b).zipped.toVector zipped: Vector[(Int, Int)] = Vector((1,4), (2,5), (3,6))

The _ (underscore) in Scala has a variety of uses, most of which are outside the scope of this document. Here we use _ to refer to an argument without a name. The following examples are equivalent:

scala> val a = Vector(1,2,3) a: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3) scala> a.map(value => println(value)) 1 2 3 scala> a.map(println(_)) 1 2 3

Int => Int declares a higher order function type which takes an Integer and returns an Integer. In this document, we’ll use higher order functions to store unevaluated universal hash functions.

scala> def square: Int => Int = { | (x:Int) => x * x | } square: Int => Int scala> square(5) res0: Int = 25

Shingles, MinHash, LSH and Jaccard Similarity, A Bottom Up Approach

This section gives an overview of the components required to calculate document similarity. Each section in this article is designed to explain the components required to implement the algorithm and to highlight how we can move from comparing huge sets of words and their word ordering (shingling) to comparing small, finite signatures to determine candidate similar documents.

Each section is designed to be concise and easy to read while favoring ease of understanding as opposed to performance. We discuss how the implementation maps to the theory and highlight when the theory diverges from the implementation. Below we show a general workflow for creating signatures using Shingling, MinHash and Locality Sensitive Hashing.

An overview of the workflow for document similarity.

Terms Used in this Document

The definitions below are covered in detail throughout the article but we provide a quick overview of the most important terms.

Jaccard Similarity — the magnitude of the set intersection divided by the set union. Measures similarity between two sets.

Shingling — the process of picking a window size and sliding the chosen window over the document such that it produces contiguous subsequences of the text under consideration. Shingle sets can be compared using Jaccard Similarity.

MinHash — compute the hashes of the text shingles N number of times, and for all sequence of hash values, choose the minimum value for each sequence offset. This effectively samples the set of hashes and reduces the amount of data required for a signature. The set of computed minimum hash values can then be used to estimate Jaccard Similarity. However, doing a pairwise comparison to determine each document similar to each other document requires order O(n2) operations.

Locality Sensitive Hashing — compute the hash of groups of MinHash values. The grouping of MinHash values hashed together is known as a band. The collection of hashed bands computed during LSH samples the MinHash values and reduces the amount of data required to determine similar documents even further. Documents can be compared by determining if a subset of their LSH buckets match. Because we hash all the values into buckets, we can obtain candidate pairs for matching similarity by determining if they share the same bucket. This can be done in order O(n) time.

An Overview of the Algorithms in an Example Program

This section will build a simple document comparison using a Shingler, MinHash, LSH and Jaccard similarity in the Scala programming language. To kick things off, the entire flow of a sample run of the algorithms used in this document are shown. We use two very simple documents which contain the strings “this is really rude” and “this is really crude”. Below we will confirm in code what our intuition suggests: the documents are indeed similar.

As far as parameters are concerned, we humbly ask the reader to bear with us, as each parameter will be explained in detail in later sections of the article. The main goal of this section is to give a complete program that executes all of the algorithmic components. The features we choose will be: character shingles of length three (k = 3), the MinHash signature will contain 100 hashes (numHashes = 100), and the similarity threshold used to pick the number of bands is 50% (threshold = 0.50). We choose an value to seed the random number generator (seed = 1337), this value is used throughout the document to ensure repeatable random number generation.

Example Output

Below we show a complete example of computing shingles, calculating Jaccard similarity, MinHashing, Locality Sensitive Hashing, and Jaccard Similarity estimation using MinHash signatures of matching LSH buckets.

Next Time

Next time, we’ll discuss the implementation details for each part of the algorithm for detecting document similarity. We’ll first start with an overview of shingling and computing document features. Then, we’ll discuss various hash functions, like djb2a and universal hash functions and show how they fit into the big picture. Finally, we’ll dive into Minhash and Locality Sensitive Hashing and describe how we can sample document features to compute fixed size signatures that can be used to compute document similarity.