Implementation of Locality Sensitive Hashing Techniques

Abstract

Locality-sensitive hashing (LSH) is a method of performing probabilistic dimension reduction of high-dimensional data. The basic idea is to hash the input items so that similar items are mapped to the same buckets with high probability (the number of buckets being much smaller than the universe of possible input items). The hashing used in LSH is different from conventional hash functions, such as those used in cryptography, as in the LSH case the goal is to maximize probability of "collision" of similar items rather than avoid collisions. Locality-sensitive hashing, in many ways, mirrors data clustering and Nearest neighbor search. The idea behind LSH is to construct a family of functions that hash objects into buckets such that objects that are similar will be hashed to the same bucket with high probability. Here, the type of the objects and the notion of similarity between them determine the particular hash function family. Typical instances include the Jaccard coefficient as similarity when the underlying objects are sets and the ℓ-2 norm as distance (i.e., dissimilarity) or the cosine/angle as similarity when the underlying objects are vectors. LSH in nearest-neighbor applications can improve performance by significant amounts.