org.openimaj.knn

Class LongNearestNeighboursExact

java.lang.Object

org.openimaj.knn.LongNearestNeighbours

org.openimaj.knn.LongNearestNeighboursExact

All Implemented Interfaces:

NearestNeighbours<long[],double[],IntDoublePair>

public class LongNearestNeighboursExact
extends LongNearestNeighbours

Exact (brute-force) k-nearest-neighbour implementation.

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	LongNearestNeighboursExact.Factory NearestNeighboursFactory for producing LongNearestNeighboursExacts.

Field Summary

Fields

Modifier and Type	Field and Description
protected LongFVComparator	distance
protected long[][]	pnts

Constructor Summary

Constructors

Constructor and Description
LongNearestNeighboursExact(long[][] pnts) Construct the LongNearestNeighboursExact over the provided dataset and using Euclidean distance.
LongNearestNeighboursExact(long[][] pnts, LongFVComparator distance) Construct the LongNearestNeighboursExact over the provided dataset with the given distance function.

Method Summary

Modifier and Type	Method and Description
double	computeDistance(long[] a, long[] b) Compute the distance between two vectors using the underlying distance comparison used by this class.
LongFVComparator	distanceComparator() Get the distance comparator
long[][]	getPoints() Get the underlying data points.
int	numDimensions() Get the number of dimensions of each vector in the dataset
void	searchKNN(List<long[]> qus, int K, int[][] indices, double[][] 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(long[][] qus, int K, int[][] indices, double[][] 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<IntDoublePair>	searchKNN(long[] 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<long[]> qus, int[] indices, double[] distances) Search for the nearest neighbour to each of the N queries, and return the index of each nearest neighbour and the respective distance.
IntDoublePair	searchNN(long[] query) Search for the nearest neighbour to the given query and return a pair containing the distance and index of that neighbour.
void	searchNN(long[][] qus, int[] indices, double[] 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.LongNearestNeighbours

distanceFunc, distanceFunc, distanceFunc, distanceFunc

Methods inherited from class java.lang.Object

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

Field Detail

pnts

protected final long[][] pnts

distance

protected final LongFVComparator distance

Constructor Detail

LongNearestNeighboursExact

public LongNearestNeighboursExact(long[][] pnts)

Construct the LongNearestNeighboursExact over the provided dataset and using Euclidean distance.

Parameters:

pnts - the dataset

LongNearestNeighboursExact

public LongNearestNeighboursExact(long[][] pnts,
                                  LongFVComparator distance)

Construct the LongNearestNeighboursExact 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

Method Detail

searchNN

public void searchNN(long[][] qus,
                     int[] indices,
                     double[] 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

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(long[][] qus,
                      int K,
                      int[][] indices,
                      double[][] 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

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<long[]> qus,
                     int[] indices,
                     double[] 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

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<long[]> qus,
                      int K,
                      int[][] indices,
                      double[][] 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

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<IntDoublePair> searchKNN(long[] 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.

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 IntDoublePair searchNN(long[] 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.

Parameters:

query - the query vector

Returns:

the distance and index of the nearest neighbour

numDimensions

public int numDimensions()

Description copied from class: LongNearestNeighbours

Get the number of dimensions of each vector in the dataset

Specified by:

numDimensions in class LongNearestNeighbours

Returns:

the number of dimensions

size

public int size()

Description copied from interface: NearestNeighbours

Get the size of the dataset

Returns:

the dataset size

getPoints

public long[][] getPoints()

Get the underlying data points.

Returns:

the data points

computeDistance

public double computeDistance(long[] a,
                              long[] b)

Compute the distance between two vectors using the underlying distance comparison used by this class.

Parameters:

a - the first vector

b - the second vector

Returns:

the distance between the two vectors

distanceComparator

public LongFVComparator distanceComparator()

Get the distance comparator

Returns:

the distance comparator