llteixeira/lshfunctions.jl

Locality-sensitive hashing (LSH) in Julia.

LSHFunctions.jl

A Julia package for locality-sensitive hashing to accelerate similarity search.

• What's LSH?
• Installation
• Supported similarity functions
• Examples

What's LSH?

Traditionally, if you have a data point x, and want to find the most similar point(s) to x in your database, you would compute the similarity between x and all of the points in your database, and keep whichever points were the most similar. For instance, this type of approach is used by the classic k-nearest neighbors algorithm. However, it has two major problems:

• The time to find the most similar point(s) to x is linear in the number of points in your database. This can make similarity search prohibitively expensive for even moderately large datasets.
• In addition, the time complexity to compute the similarity between two datapoints is typically linear in the number of dimensions of those datapoints. If your data are high-dimensional (i.e. in the thousands to millions of dimensions), every similarity computation you perform can be fairly costly.

Locality-sensitive hashing (LSH) is a technique for accelerating these kinds of similarity searches. Instead of measuring how similar your query point is to every point in your database, you calculate a few hashes of the query point and only compare it against those points with which it experiences a hash collision. Locality-sensitive hash functions are randomly generated, with the fundamental property that as the similarity between x and y increases, the probability of a hash collision between x and y also increases.

Installation

You can install LSHFunctions.jl from the Julia REPL with

pkg> add LSHFunctions

Supported similarity functions

So far, there are hash functions for the similarity functions:

• Cosine similarity (SimHash)
• Jaccard similarity (MinHash)
• L1 (Manhattan / "taxicab") distance: L1Hash
• L2 (Euclidean) distance: L2Hash
• Inner product
  • SignALSH (recommended)
  • MIPSHash
• Function-space hashes (supports L1, L2, and cosine similarity)
  • MonteCarloHash
  • ChebHash

This package still needs a lot of work, including improvement to the documentation and API.

Examples

The easiest way to start constructing new hash functions is by calling LSHFunction with the following syntax:

hashfn = LSHFunction(similarity function,
                     number of hash functions to generate;
                     [LSH family-specific keyword arguments])

For example, the following snippet generates 10 locality-sensitive hash functions (bundled together into a single SimHash ) for cosine similarity:

julia> using LSHFunctions;

julia> hashfn = LSHFunction(cossim, 10);

julia> n_hashes(hashfn)
10

julia> similarity(hashfn)
cossim

You can hash inputs by calling hashfn():

julia> x = randn(128);

julia> x_hashes = hashfn(x);

For more details, check out the LSHFunctions.jl documentation.