org.openimaj.knn.lsh

Class LSHNearestNeighbours<OBJECT>

java.lang.Object

org.openimaj.knn.lsh.LSHNearestNeighbours<OBJECT>

Type Parameters:

OBJECT - Type of object being stored.

All Implemented Interfaces:

IncrementalNearestNeighbours<OBJECT,float[],IntFloatPair>, NearestNeighbours<OBJECT,float[],IntFloatPair>

public class LSHNearestNeighbours<OBJECT>
extends Object
implements IncrementalNearestNeighbours<OBJECT,float[],IntFloatPair>

Nearest-neighbours based on Locality Sensitive Hashing (LSH). A number of internal hash-tables are created with an associated hash-code (which is usually a composite of multiple locality sensitive hashes). For a given query, the hash-code of the query object computed for each hash function and a lookup is made in each table. The set of matching items drawn from the tables is then combined and sorted by distance (and trimmed if necessary) before being returned.

Note: This object is not thread-safe. Multiple insertions or mixed insertions and searches should not be performed concurrently without external locking.

Author:

Jonathon Hare (jsh2@ecs.soton.ac.uk)

Field Summary

Fields

Modifier and Type	Field and Description
protected List<OBJECT>	data
protected DistanceComparator<OBJECT>	distanceFcn
protected List<org.openimaj.knn.lsh.LSHNearestNeighbours.Table<OBJECT>>	tables

Constructor Summary

Constructors

Constructor and Description
LSHNearestNeighbours(HashFunctionFactory<OBJECT> factory, int numTables, DistanceComparator<OBJECT> distanceFcn) Construct with the given hash function factory which will be used to initialize the requested number of hash tables.
LSHNearestNeighbours(List<HashFunction<OBJECT>> tableHashes, DistanceComparator<OBJECT> distanceFcn) Construct with the given hash functions and distance function.

Method Summary

Modifier and Type	Method and Description
int	add(OBJECT o) Add a single data item
void	addAll(Collection<OBJECT> d) Insert data into the tables
int[]	addAll(List<OBJECT> d) Insert all the given data
void	addAll(OBJECT[] d) Insert data into the tables
OBJECT	get(int i) Get the data item at the given index.
int[]	getBucketId(OBJECT point) Compute identifiers of the buckets in which the given point belongs for all the tables.
int[][]	getBucketId(OBJECT[] data) Compute identifiers of the buckets in which the given points belong for all the tables.
List<OBJECT>	getData() Get a read-only view of the underlying data.
int	numTables() Get the number of hash tables
gnu.trove.set.hash.TIntHashSet	search(OBJECT data) Search for a similar data item in the underlying tables and return all matches
gnu.trove.set.hash.TIntHashSet[]	search(OBJECT[] data) Search for similar data in the underlying tables and return all matches
void	searchKNN(List<OBJECT> qus, int K, int[][] argmins, float[][] mins) Search for the K nearest neighbours to each of the N queries, and return the indices of each nearest neighbour and their respective distances.
void	searchKNN(OBJECT[] qus, int K, int[][] argmins, float[][] mins) Search for the K nearest neighbours to each of the N queries, and return the indices of each nearest neighbour and their respective distances.
List<IntFloatPair>	searchKNN(OBJECT query, int K) Search for the K nearest neighbours to the given query and return an ordered list of pairs containing the distance and index of each neighbour.
void	searchNN(List<OBJECT> qus, int[] argmins, float[] mins) Search for the nearest neighbour to each of the N queries, and return the index of each nearest neighbour and the respective distance.
IntFloatPair	searchNN(OBJECT query) Search for the nearest neighbour to the given query and return a pair containing the distance and index of that neighbour.
void	searchNN(OBJECT[] qus, int[] argmins, float[] mins) Search for the nearest neighbour to each of the N queries, and return the index of each nearest neighbour and the respective distance.
int	size() Get the size of the dataset

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

distanceFcn

protected DistanceComparator<OBJECT> distanceFcn

tables

protected List<org.openimaj.knn.lsh.LSHNearestNeighbours.Table<OBJECT>> tables

data

protected List<OBJECT> data

Constructor Detail

LSHNearestNeighbours

public LSHNearestNeighbours(List<HashFunction<OBJECT>> tableHashes,
                            DistanceComparator<OBJECT> distanceFcn)

Construct with the given hash functions and distance function. One table will be created per hash function.

Parameters:

tableHashes - The hash functions

distanceFcn - The distance function

LSHNearestNeighbours

public LSHNearestNeighbours(HashFunctionFactory<OBJECT> factory,
                            int numTables,
                            DistanceComparator<OBJECT> distanceFcn)

Construct with the given hash function factory which will be used to initialize the requested number of hash tables.

Parameters:

factory - The hash function factory.

numTables - The number of requested tables.

distanceFcn - The distance function.

Method Detail

numTables

public int numTables()

Get the number of hash tables

Returns:

The number of hash tables

addAll

public void addAll(Collection<OBJECT> d)

Insert data into the tables

Parameters:

d - the data

addAll

public void addAll(OBJECT[] d)

Insert data into the tables

Parameters:

d - the data

add

public int add(OBJECT o)

Description copied from interface: IncrementalNearestNeighbours

Add a single data item

Specified by:

add in interface IncrementalNearestNeighbours<OBJECT,float[],IntFloatPair>

Parameters:

o - the object to add

Returns:

the index of the added data

search

public gnu.trove.set.hash.TIntHashSet[] search(OBJECT[] data)

Search for similar data in the underlying tables and return all matches

Parameters:

data - the points

Returns:

matched ids

search

public gnu.trove.set.hash.TIntHashSet search(OBJECT data)

Search for a similar data item in the underlying tables and return all matches

Parameters:

data - the point

Returns:

matched ids

getBucketId

public int[][] getBucketId(OBJECT[] data)

Compute identifiers of the buckets in which the given points belong for all the tables.

Parameters:

data - the points

Returns:

the bucket identifiers

getBucketId

public int[] getBucketId(OBJECT point)

Compute identifiers of the buckets in which the given point belongs for all the tables.

Parameters:

point - the point

Returns:

the bucket identifiers

searchNN

public void searchNN(OBJECT[] qus,
                     int[] argmins,
                     float[] mins)

Description copied from interface: NearestNeighbours

Search for the nearest neighbour to each of the N queries, and return the index of each nearest neighbour and the respective distance.

For efficiency, to use this method, you need to pre-construct the arrays for storing the results outside of the method and pass them in as arguments.

If a nearest-neighbour cannot be determined, it will have an index value of -1

Specified by:

searchNN in interface NearestNeighbours<OBJECT,float[],IntFloatPair>

Parameters:

qus - An array of N query vectors

argmins - The return N-dimensional array for holding the indices of the nearest neighbour of each respective query.

mins - The return N-dimensional array for holding the distances of the nearest neighbour to each respective query.

searchKNN

public void searchKNN(OBJECT[] qus,
                      int K,
                      int[][] argmins,
                      float[][] mins)

Description copied from interface: NearestNeighbours

Search for the K nearest neighbours to each of the N queries, and return the indices of each nearest neighbour and their respective distances.

For efficiency, to use this method, you need to pre-construct the arrays for storing the results outside of the method and pass them in as arguments.

If a k-th nearest-neighbour cannot be determined, it will have an index value of -1

Specified by:

searchKNN in interface NearestNeighbours<OBJECT,float[],IntFloatPair>

Parameters:

qus - An array of N query vectors

K - the number of neighbours to find

argmins - The return N*K-dimensional array for holding the indices of the K nearest neighbours of each respective query.

mins - The return N*K-dimensional array for holding the distances of the nearest neighbours of each respective query.

searchNN

public void searchNN(List<OBJECT> qus,
                     int[] argmins,
                     float[] mins)

Description copied from interface: NearestNeighbours

Search for the nearest neighbour to each of the N queries, and return the index of each nearest neighbour and the respective distance.

For efficiency, to use this method, you need to pre-construct the arrays for storing the results outside of the method and pass them in as arguments.

If a nearest-neighbour cannot be determined, it will have an index value of -1

Specified by:

searchNN in interface NearestNeighbours<OBJECT,float[],IntFloatPair>

Parameters:

qus - An array of N query vectors

argmins - The return N-dimensional array for holding the indices of the nearest neighbour of each respective query.

mins - The return N-dimensional array for holding the distances of the nearest neighbour to each respective query.

searchKNN

public void searchKNN(List<OBJECT> qus,
                      int K,
                      int[][] argmins,
                      float[][] mins)

Description copied from interface: NearestNeighbours

Search for the K nearest neighbours to each of the N queries, and return the indices of each nearest neighbour and their respective distances.

For efficiency, to use this method, you need to pre-construct the arrays for storing the results outside of the method and pass them in as arguments.

If a k-th nearest-neighbour cannot be determined, it will have an index value of -1

Specified by:

searchKNN in interface NearestNeighbours<OBJECT,float[],IntFloatPair>

Parameters:

qus - An array of N query vectors

K - the number of neighbours to find

argmins - The return N*K-dimensional array for holding the indices of the K nearest neighbours of each respective query.

mins - The return N*K-dimensional array for holding the distances of the nearest neighbours of each respective query.

size

public int size()

Description copied from interface: NearestNeighbours

Get the size of the dataset

Specified by:

size in interface NearestNeighbours<OBJECT,float[],IntFloatPair>

Returns:

the dataset size

getData

public List<OBJECT> getData()

Get a read-only view of the underlying data.

Returns:

a read-only view of the underlying data.

get

public OBJECT get(int i)

Get the data item at the given index.

Parameters:

i - The index

Returns:

the retrieved object

addAll

public int[] addAll(List<OBJECT> d)

Description copied from interface: IncrementalNearestNeighbours

Insert all the given data

Specified by:

addAll in interface IncrementalNearestNeighbours<OBJECT,float[],IntFloatPair>

Parameters:

d - the data

Returns:

the indexes of the added data

searchKNN

public List<IntFloatPair> searchKNN(OBJECT query,
                                    int K)

Description copied from interface: NearestNeighbours

Search for the K nearest neighbours to the given query and return an ordered list of pairs containing the distance and index of each neighbour.

If k neighbours cannot be determined, then the resultant list might have fewer than k elements.

Specified by:

searchKNN in interface NearestNeighbours<OBJECT,float[],IntFloatPair>

Parameters:

query - the query vector

K - the number of neighbours to search for

Returns:

the top K nearest neighbours ordered by increasing distance

searchNN

public IntFloatPair searchNN(OBJECT query)

Description copied from interface: NearestNeighbours

Search for the nearest neighbour to the given query and return a pair containing the distance and index of that neighbour.

If the nearest-neighbour cannot be determined null will be returned.

Specified by:

searchNN in interface NearestNeighbours<OBJECT,float[],IntFloatPair>

Parameters:

query - the query vector

Returns:

the distance and index of the nearest neighbour