Awesome

LSH

Installation

This package requires julia version 0.4 which is currently under development. See http://julialang.org/downloads/ for instructions on how to download a latest nightly release for all major platforms.

After installing julia, this package can be installed with:

Pkg.clone("https://github.com/Keno/LSH.jl")
# This is currently needed while changes to DataStructures.jl are awaiting upstreaming
Pkg.checkout("DataStructures","kf/lsh")

API

LSHTable

The main entry point to this package is the LSHTable struct, which can be constructed as

T = LSHTable(R,hashes,data; progress=true)

where R is the desired query radius, i.e. the R in an R-NN data structure, hashes is an array of locality sensitive hash function (see below for how to create these) and data is the data set to be added to the locality sensitive hash table. data can be specified either as a Vector of vectors, with each contained vector representing a data point, or as a matrix with the coordinates of the points given by the rows of the matrix.

The data structure can be queried via it's getindex method:

found_points = T[q]

where q is the coordinate vector of query points and found_points is the list of found points.

Hashes

Currently this package supports two kinds of hash functions, both as defined in [AM04]. Both kinds are made up of tuples of hash functions based on p-stable distributions, though the first method (dubbed g-functions) requires O(kdL) compute whereas the second method (dubbed u-functions) can be constructed in O(kdm) where m is appriximately sqrt(L). The hash arrays can be constructed using:

hashesg = createHashesAM04(d,w,k,L,R) # Create g functions with the given parameters
hashesu = createUHashesAM04(d,w,k,L,R) # Create u functions with the given parameters