lsh-rs (Locality Sensitive Hashing)

Locality sensitive hashing can help retrieving Approximate Nearest Neighbors in sub-linear time.

For more information on the subject see:

Implementations

Base LSH
- Signed Random Projections (Cosine similarity)
- L2 distance
- MIPS (Dot products/ Maximum Inner Product Search)
- MinHash (Jaccard Similarity)
Multi Probe LSH
- Step wise probing
  - SRP (only bit shifts)
- Query directed probing
  - L2
  - MIPS
Generic numeric types

Getting started

use lsh_rs::LshMem;
// 2 rows w/ dimension 3.
let p = &[vec![1., 1.5, 2.],
        vec![2., 1.1, -0.3]];

// Do one time expensive preprocessing.
let n_projections = 9;
let n_hash_tables = 30;
let dim = 10;
let dim = 3;
let mut lsh = LshMem::new(n_projections, n_hash_tables, dim)
    .srp()
    .unwrap();
lsh.store_vecs(p);

// Query in sublinear time.
let query = &[1.1, 1.2, 1.2];
lsh.query_bucket(query);

Documentation

Read the Rust docs.
Read the Python docs for the Python bindings.

Python

At the moment, the Python bindings are only compiled for Linux x86_64 systems.

$ pip install floky

from floky import SRP
import numpy as np

N = 10000
n = 100
dim = 10

# Generate some random data points
data_points = np.random.randn(N, dim)

# Do a one time (expensive) fit.
lsh = SRP(n_projections=19, n_hash_tables=10)
lsh.fit(data_points)

# Query approximated nearest neigbors in sub-linear time
query = np.random.randn(n, dim)
results = lsh.predict(query)

License

ritchie46/lsh-rs

About

Topics

Resources

License

Uh oh!

Stars

Watchers

Forks

Releases

Packages 0

Uh oh!

Contributors 5

Languages

Packages