h1. TarsosLSH - Locality Sensitive Hashing (LSH) in Java
TarsosLSH is a Java library implementing sub-linear nearest neigbour search algorithms. It contains both an approximate and an exact search algorithm. The first, Locality-sensitive Hashing (LSH) is a randomized approximate search algorithm for a number of search spaces. The second, Multi-index hashing is an exact nearest neigbour search algorithm which is limited to Hamming space.
Locality-sensitive Hashing (LSH), a practical nearest neighbour search algorithm for multidimensional vectors that operates in sublinear time. It supports several Locality Sensitive Hashing (LSH) families: the Euclidean hash family (L2), city block hash family (L1) and cosine hash family. The library tries to hit the sweet spot between being capable enough to get real tasks done, and compact enough to serve as a demonstration on how LSH works.
Multi-index hashing is an exact, sub-linear nearest neighbour search algorithm in hamming space. It is a simple algorithm that seeks a balance between storage space requirements and query performance.
h2. Quickly Getting Started with TarsosLSH
Head over to the "TarsosLSH release repository":http://0110.be/releases/TarsosLSH/ and download the latest "TarsosLSH library":http://0110.be/releases/TarsosLSH/TarsosLSH-latest/TarsosLSH-latest.jar. Consult the "TarsosLSH API documentation":http://0110.be/releases/TarsosLSH/TarsosLSH-latest/TarsosLSH-latest-Documentation/. If you, for some reason, want to build from source, you need "Apache Ant":http://ant.apache.org/ and "git":http://git-scm.com/ installed on your system. The following commands fetch the source and build the library and example jars:
git clone https://[email protected]/JorenSix/TarsosLSH.git cd TarsosLSH/build ant #Builds the core TarsosLSH library ant javadoc #build the API documentation
When everything runs correctly you should be able to run the command line application, and have the latest version of the TarsosLSH library for inclusion in your projects. Also, the Javadoc documentation for the API should be available in TarsosLSH/doc. Drop me a line (joren _ at _ 0110 _ dot _ be) if you use TarsosLSH in your project. Always nice to hear how this software is used.
The fastest way to get something on your screen is executing this on your command line: @java - jar [email protected] this lets LSH run on a random data set. The full reference of the command line application is included below:
Name TarsosLSH: finds the nearest neighbours in a data set quickly, using LSH. Synopsis java - jar TarsosLSH.jar [options] Description Tries to find nearest neighbours for each vector in the query file, using Euclidean (L2) distance by default. Both dataset.txt and queries.txt have a similar format: an optional identifier for the vector and a list of N coordinates (which should be doubles). [Identifier] coord1 coord2 ... coordN [Identifier] coord1 coord2 ... coordN For an example data set with two elements and 4 dimensions: Hans 12 24 18.5 -45.6 Jane 13 19 -12.0 49.8 Options are: -d dataset.txt The dataset with vectors to store in the hash table -q queries.txt A list of vectors to query against the stored dataset -f cos|l1|l2 Defines the hash family to use: l1 City block hash family (L1) l2 Euclidean hash family(L2) cos Cosine distance hash family -r radius Defines the radius in which near neighbours should be found. Should be a double. By default a reasonable radius is determined automatically. -h n_hashes An integer that determines the number of hashes to use. By default 4, 32 for the cosine hash family. -t n_tables An integer that determines the number of hash tables, each with n_hashes, to use. By default 4. -n n_neighbours Number of neighbours in the neighbourhood, defaults to 3. -b Benchmark the settings. --help Prints this helpful message. Examples Search for nearest neighbours using the l2 hash family with a radius of 500 and utilizing 5 hash tables, each with 3 hashes. java -jar TarsosLSH.jar -f l2 -r 500 -h 3 -t 5 -d dataset.txt -q queries.txt
h2. Source Code Organization
The source tree is divided in three directories:
The TarsosLSH license is distributed under the LGPL license.
h2. Further Reading
This section includes a links to resources used to implement this library.
For more information on Multi-Index Hashing:
h2. Change log