jorensix / tarsoslsh

A Java library implementing practical nearest neighbour search algorithm for multidimensional vectors that operates in sublinear time. It implements Locality-sensitive Hashing (LSH) and multi index hashing for hamming space.

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 (L₂), city block hash family (L₁) 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.

Quickly Getting Started with TarsosLSH

Head over to the TarsosLSH release repository and download the latest TarsosLSH library. Consult the TarsosLSH API documentation. If you, for some reason, want to build from source, you need Apache Ant and git 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 TarsosLSH.jar 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 (L<sub>2</sub>) 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 (L<sub>1</sub>)
			l2	Euclidean hash family(L<sub>2</sub>)
			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

Source Code Organization

The source tree is divided in three directories:

• src contains the source files, the core functionality.
  • src/be/tarsos/lsh Contains the LSH implementation
  • src/be/tarsos/mih Contains an implementation of a multi index hash algorithm
• test contains unit tests for some of the functionality.
• build contains ANT build files. Either to build Java documentation and runnable JAR-files.

License

The TarsosLSH license is distributed under the LGPL license.

Further Reading

This section includes a links to resources used to implement this library.

• The LSH-page maintained by Alexandr Andoni contains pointers to good resources:
  • Locality-Sensitive Hashing Scheme Based on p-Stable Distributions a chapter by Alexandr Andoni, Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab Mirrokni which appeared in the book Nearest Neighbor Methods in Learning and Vision: Theory and Practice, by T. Darrell and P. Indyk and G. Shakhnarovich (eds.), MIT Press, 2006.
  • Similarity Search in High Dimensions via Hashing The original LSH Paper for hamming distance by Gionis, Aristides and Indyk, Piotr and Motwani, Rajeev.
• Locality-Sensitive Hashing for Finding Nearest Neighbors a good introduction of LSH by Malcom Slaney & Michael Casey
• Finding Similar Items, Chapter Three of “Mining of Massive Datasets” by Anand Rajaraman and Jeff Ullman is a textbook introducing the LSH concept.
• Szudzik pairing functions by Matthew Szudzik. Explains how integer hashes can be combined deterministically to form a reversible, unique new hash.

For more information on Multi-Index Hashing:

• Fast Search in Hamming Space with Multi-Index Hashing, Mohammad Norouzi, Ali Punjani, David Fleet – IEEE Computer Vision and Pattern Recognition (CVPR), 2012.
• An extended version of Fast Exact Search in Hamming Space with Multi-Index Hashing
• Compact Discrete Representations for Scalable Similarity Search
• A github repository with a Multi-Index Hashing C++ implementation

Dependencies

TarsosLSH relies on MapDB for storage which in turn depends on eclipse collections.

Change log

Version 0.5

2013-04-17

First release which includes several LSH families.

Version 0.6

2013-06-13

Added serialization options to store LSH hashes, which makes the library more practical in real-world scenario’s. Later database support should be added.

Version 0.7

2015-03-16

Maintenance release with changed package names and small fixes to the documentation and build file.

Version 0.8

2017-03-17

Adds an implementation of a Hamming space LSH scheme.

Version 0.9

2017-04-21

Adds an implementation of a Hamming space multi index hasher algorithm as described in Fast Exact Search in Hamming Space with Multi-Index Hashing .

tarsoslsh's Issues

The meaning of the parameter m

who can explain the meaning of the parameter m?

Dealing with missing data

I am contemplating using LSH in my application, but I am unsure how to deal with absent/missing data in a vector. The nearest neighbor imputation implies that this type of algorithm deals with this scenario, but how would I go about implementing it?

Is it as simple as not calling "set" for that dimension?

EuclideanDistance doesn't seem to work correctly

The command line runner help is incorrect regarding EuclideanDistance:

if(radius == 0 && hashFamilyType.equalsIgnoreCase("l1")){
  measure = new CityBlockDistance(); 
  ...
} else if (radius == 0 && hashFamilyType.equalsIgnoreCase("l2")){
  measure = new CityBlockDistance();
  ...
}

CityBlockDistance is used for both L1 and L2

how to "Drop me a Line"?

I use this lib in my homework for Image and Audio Search ,Thank U very much.
“Drop me a line if you use TarsosLSH in your project. Always nice to hear how this software is used.” but I do not know how to do it .I have to write it here.
By the way, I think as a lib, some class lost some method .
For example:
I add "public Vector(String key,double[] double){}" to create a vector immediately(this is very important , I think)
I add some method to get dataset from memory instead of disk file, like:
“public LSH createIndex(double radius,String hashFamilyType,int numberOfHashes,int numberOfHashTables,int numberOfNeighbours,List dataset){}” for more convenient.

Calculation of CityBlockHash

In families/CityBlockHash.java, you calculate the hash with the following code (line 51):

hash[d] = (int) (vector.get(d)-randomPartition.get(d) / Double.valueOf(w));

I could be wrong here, but would you want parenthesis around the numerator? Otherwise order of operations takes precedence, which I'm not sure is correct.

Thanks. I'd be happy to put in a pull request for you, if need be.

The DistanceMeasure for l1 and l2 should be swapped.

In CommandLineInterface.java

if(radius == 0 && hashFamilyType.equalsIgnoreCase("l1")){
    measure = new EuclideanDistance();
    radius = LSH.determineRadius(dataset, measure, timeout);
} else if (radius == 0 && hashFamilyType.equalsIgnoreCase("l2")){
    measure = new CityBlockDistance();
    radius = LSH.determineRadius(dataset, measure, timeout);
}

The position of EuclideanDistance and CityBlockDistance should be swapped?

How to use TarsosLSH for text documents

I would like search for similar text documents using TarsosLSH. Maybe you could suggest some techniques, how to transform text to vector, suitable for this library?

Thank you!

GC overhead limit exceeded

Even after using 13g of memory I get "GC overhead limit exceeded" exception with following stack trace:
Picked up _JAVA_OPTIONS: -Xms2g -Xmx13g -Xss100M -XX:MaxPermSize=3g
Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded
at java.util.Arrays.copyOfRange(Arrays.java:2694)
at java.lang.String.(String.java:203)
at java.lang.String.substring(String.java:1913)
at java.lang.String.split(String.java:2288)
at java.lang.String.split(String.java:2355)
at be.tarsos.lsh.util.FileUtils.readCSVFile(Unknown Source)
at be.tarsos.lsh.LSH.readDataset(Unknown Source)
at be.tarsos.lsh.CommandLineInterface.parseArguments(Unknown Source)
at be.tarsos.lsh.LSH.main(Unknown Source)

My dataset size is 4GB, it contains 15201 vectors. I run with following options "java -jar TarsosLSH-0.7.jar -f l2 -h 8 -t 32 -n 15 -d tfVectorFor105G -q tfVectorQueriesOn105g"

How to use LSH in Hamming

As a naive learner I want to ask a naive question that how to use LSH in Hamming. I have tried use BinLSH, however it can not run successfully, the format is as below and the dataset is your test dataset.

String[] test = new String[]{"-d","D:/TarsosLSH/build/dataset.txt","-q","D:/TarsosLSH/build/queries.txt"};
BinCommandLineInterface cli = new BinCommandLineInterface(test);

the problem is:
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0

Could you tell me how to solve this problem? I will be appreciated it if you give me the answer as soon as possible.Thank you.