org.openimaj.knn.approximate

Class DoubleNearestNeighboursKDTree

java.lang.Object

org.openimaj.knn.DoubleNearestNeighbours

org.openimaj.knn.approximate.DoubleNearestNeighboursKDTree

All Implemented Interfaces:

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

public class DoubleNearestNeighboursKDTree
extends DoubleNearestNeighbours

Fast Nearest-Neighbours for double data using an ensemble of Best-Bin-First KDTrees.

Implementation inspired by http://www.robots.ox.ac.uk/~vgg/software/fastann/

Author:

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

Bibliography:

• Plain Text
• BibTex
• OpenIMAJ Annotation

M. Muja and D. G. Lowe. Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration. International Conference on Computer Vision Theory and Application VISSAPP'09). INSTICC Press. pp331-340. 2009.

@inproceedings{ Muja2009
 author = {{Marius Muja} and {David G. Lowe}}
 title = {Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration}
 year = {2009}
 booktitle = {International Conference on Computer Vision Theory and Application VISSAPP'09)}
 pages = {331--340}
 publisher = {INSTICC Press}
}

@Reference(type=Inproceedings,
           author={"Marius Muja","David G. Lowe"},
           title="Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration",
           year="2009",
           booktitle="International Conference on Computer Vision Theory and Application VISSAPP\'09)",
           pages={"331","340"},
           publisher="INSTICC Press")

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	DoubleNearestNeighboursKDTree.Factory NearestNeighboursFactory for producing DoubleNearestNeighboursKDTrees.

Field Summary

Fields

Modifier and Type	Field and Description
static int	DEFAULT_NCHECKS The default number of checks performed during search when in exact mode.
static int	DEFAULT_NTREES The default number of kdtrees when not in exact mode.
DoubleKDTreeEnsemble	kdt The ensemble of KDTrees
int	nchecks The number of checks

Constructor Summary

Constructors

Constructor and Description
DoubleNearestNeighboursKDTree(double[][] pnts, int ntrees, int nchecks) Construct the DoubleNearestNeighboursKDTree with the given options.

Method Summary

Modifier and Type	Method and Description
int	numDimensions() Get the number of dimensions of each vector in the dataset
void	searchKNN(double[][] qus, int K, int[][] argmins, double[][] 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<IntDoublePair>	searchKNN(double[] 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	searchKNN(List<double[]> qus, int K, int[][] argmins, double[][] 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.
IntDoublePair	searchNN(double[] query) Search for the nearest neighbour to the given query and return a pair containing the distance and index of that neighbour.
void	searchNN(double[][] qus, int[] argmins, double[] mins) Search for the nearest neighbour to each of the N queries, and return the index of each nearest neighbour and the respective distance.
void	searchNN(List<double[]> qus, int[] argmins, double[] 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 org.openimaj.knn.DoubleNearestNeighbours

distanceFunc, distanceFunc, distanceFunc, distanceFunc

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_NCHECKS

public static final int DEFAULT_NCHECKS

The default number of checks performed during search when in exact mode.

See Also:

Constant Field Values

DEFAULT_NTREES

public static final int DEFAULT_NTREES

The default number of kdtrees when not in exact mode.

See Also:

Constant Field Values

kdt

public final DoubleKDTreeEnsemble kdt

The ensemble of KDTrees

nchecks

public final int nchecks

The number of checks

Constructor Detail

DoubleNearestNeighboursKDTree

public DoubleNearestNeighboursKDTree(double[][] pnts,
                                     int ntrees,
                                     int nchecks)

Construct the DoubleNearestNeighboursKDTree with the given options.

Parameters:

pnts - the data

ntrees - the number of trees

nchecks - the number of checks during search

Method Detail

numDimensions

public int numDimensions()

Description copied from class: DoubleNearestNeighbours

Get the number of dimensions of each vector in the dataset

Specified by:

numDimensions in class DoubleNearestNeighbours

Returns:

the number of dimensions

size

public int size()

Description copied from interface: NearestNeighbours

Get the size of the dataset

Returns:

the dataset size

searchKNN

public void searchKNN(double[][] qus,
                      int K,
                      int[][] argmins,
                      double[][] 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

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(double[][] qus,
                     int[] argmins,
                     double[] 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

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

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

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 List<IntDoublePair> searchKNN(double[] 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(double[] 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