org.openimaj.knn

Class ObjectNearestNeighboursExact<T>

java.lang.Object

org.openimaj.knn.ObjectNearestNeighbours<T>

org.openimaj.knn.ObjectNearestNeighboursExact<T>

Type Parameters:

T - Type of object being compared.

All Implemented Interfaces:

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

public class ObjectNearestNeighboursExact<T>
extends ObjectNearestNeighbours<T>
implements IncrementalNearestNeighbours<T,float[],IntFloatPair>

Exact (brute-force) k-nearest-neighbour implementation for objects with a compatible DistanceComparator.

Author:

Jonathon Hare (jsh2@ecs.soton.ac.uk), Sina Samangooei (ss@ecs.soton.ac.uk)

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	ObjectNearestNeighboursExact.Factory<T> NearestNeighboursFactory for producing ObjectNearestNeighboursExacts.

Field Summary

Fields

Modifier and Type	Field and Description
protected List<T>	pnts

Fields inherited from class org.openimaj.knn.ObjectNearestNeighbours

distance

Constructor Summary

Constructors

Constructor and Description
ObjectNearestNeighboursExact(DistanceComparator<T> distance) Construct any empty ObjectNearestNeighboursExact with the given distance function.
ObjectNearestNeighboursExact(List<T> pnts, DistanceComparator<? super T> distance) Construct the ObjectNearestNeighboursExact over the provided dataset with the given distance function.
ObjectNearestNeighboursExact(T[] pnts, DistanceComparator<? super T> distance) Construct the ObjectNearestNeighboursExact over the provided dataset with the given distance function.

Method Summary

Modifier and Type	Method and Description
int	add(T o) Add a single data item
int[]	addAll(List<T> d) Insert all the given data
void	searchKNN(List<T> qus, int K, int[][] indices, float[][] distances) 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(T[] qus, int K, int[][] indices, float[][] distances) 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(T 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<T> qus, int[] indices, float[] distances) 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(T query) Search for the nearest neighbour to the given query and return a pair containing the distance and index of that neighbour.
void	searchNN(T[] qus, int[] indices, float[] distances) 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 org.openimaj.knn.ObjectNearestNeighbours

distanceComparator, distanceFunc

Methods inherited from class java.lang.Object

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

Field Detail

pnts

protected final List<T> pnts

Constructor Detail

ObjectNearestNeighboursExact

public ObjectNearestNeighboursExact(List<T> pnts,
                                    DistanceComparator<? super T> distance)

Construct the ObjectNearestNeighboursExact over the provided dataset with the given distance function.

Note: If the distance function provides similarities rather than distances they are automatically inverted.

Parameters:

pnts - the dataset

distance - the distance function

ObjectNearestNeighboursExact

public ObjectNearestNeighboursExact(T[] pnts,
                                    DistanceComparator<? super T> distance)

Construct the ObjectNearestNeighboursExact over the provided dataset with the given distance function.

Note: If the distance function provides similarities rather than distances they are automatically inverted.

Parameters:

pnts - the dataset

distance - the distance function

ObjectNearestNeighboursExact

public ObjectNearestNeighboursExact(DistanceComparator<T> distance)

Construct any empty ObjectNearestNeighboursExact with the given distance function.

Note: If the distance function provides similarities rather than distances they are automatically inverted.

Parameters:

distance - the distance function

Method Detail

searchNN

public void searchNN(T[] qus,
                     int[] indices,
                     float[] distances)

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<T,float[],IntFloatPair>

Parameters:

qus - An array of N query vectors

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

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

searchKNN

public void searchKNN(T[] qus,
                      int K,
                      int[][] indices,
                      float[][] distances)

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<T,float[],IntFloatPair>

Parameters:

qus - An array of N query vectors

K - the number of neighbours to find

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

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

searchNN

public void searchNN(List<T> qus,
                     int[] indices,
                     float[] distances)

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<T,float[],IntFloatPair>

Parameters:

qus - An array of N query vectors

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

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

searchKNN

public void searchKNN(List<T> qus,
                      int K,
                      int[][] indices,
                      float[][] distances)

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<T,float[],IntFloatPair>

Parameters:

qus - An array of N query vectors

K - the number of neighbours to find

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

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

searchKNN

public List<IntFloatPair> searchKNN(T 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<T,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(T 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<T,float[],IntFloatPair>

Parameters:

query - the query vector

Returns:

the distance and index of the nearest neighbour

size

public int size()

Description copied from interface: NearestNeighbours

Get the size of the dataset

Specified by:

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

Returns:

the dataset size

addAll

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

Description copied from interface: IncrementalNearestNeighbours

Insert all the given data

Specified by:

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

Parameters:

d - the data

Returns:

the indexes of the added data

add

public int add(T o)

Description copied from interface: IncrementalNearestNeighbours

Add a single data item

Specified by:

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

Parameters:

o - the object to add

Returns:

the index of the added data