Locality Sensitive Hashing

Minhashing a characteristic matrix (M) of document shingles effectively addresses the component of large-scale document similarity tasks that impacted by a high dimensionality of unique tokens used to characterize a document. This is done by compressing documents into much smaller signature matrices (S)–the manner by which this is done depends on how the two main stages (i.e., n-permutations and sampling of M) are done. Common choices of permuation are: (1) a true permutation of all k rows in a characteristic matrix, (2) a hashing of k row values into a new “permutation”–each resulting to tradeoffs between the quality similarity approximations, and computational complexity. The same tradeoffs are present in choosing a sampling step: (1) taking all k rows of of the characterisitic matrix, (2) taking only m of k rows of the characteristic matrix, or (3) dividing k into groups of m rows and applying the permutation step in each group.

Despite gains argued by Minhashing, it may still be a challenge to find the pairs with the greatest similarity efficiently. Suppose we have $n$ documents and want to find all similar documents in such a corpus. We take all pairwise combinations of $n$ documents–resulting to $(\genfrac{}{}{0ex}{}{n}{2})$ interactions which approximates to a $O(n^2)$ complexity for very high values of $n$. See below:

$$(\genfrac{}{}{0ex}{}{n}{2})=\frac{n!}{(n-2!)2!}=\frac{n(n-1)(n-2)!}{(n-2)!2!}=\frac{n(n-1)}{2}\approx n^2$$

Note: The above approximation pertains to many-to-many similarity search problems. A one-to-many version at best is $O(n)$ in time complexity.

To address the approximate quadratic $O(n^2)$ complexity–or in the case of a one-to-many comparison a linear $O(n)$ complexity, we can instead focus on documents (i.e. sets, items) that are most likely similar–known as candidate pairs. This is what locality-sensitive hashing (a.k.a. nearest-neighbor search) proposes–a bucketing together of likely similar objects to allow for a localized (i.e., selective) comparison.

In the next few sections, we shall:

1. Discuss the theory of locality-sensitive functions

2. Illustrate the use of such functions in the context of documents Jaccard similarity.