@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") public class DoubleNearestNeighboursKDTree extends DoubleNearestNeighbours
Implementation inspired by http://www.robots.ox.ac.uk/~vgg/software/fastann/
| Modifier and Type | Class and Description |
|---|---|
static class |
DoubleNearestNeighboursKDTree.Factory
NearestNeighboursFactory for producing
DoubleNearestNeighboursKDTrees. |
| 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 and Description |
|---|
DoubleNearestNeighboursKDTree(double[][] pnts,
int ntrees,
int nchecks)
Construct the DoubleNearestNeighboursKDTree with the given options.
|
| 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
|
distanceFunc, distanceFunc, distanceFunc, distanceFuncpublic static final int DEFAULT_NCHECKS
public static final int DEFAULT_NTREES
public final DoubleKDTreeEnsemble kdt
public final int nchecks
public DoubleNearestNeighboursKDTree(double[][] pnts, int ntrees, int nchecks)
pnts - the datantrees - the number of treesnchecks - the number of checks during searchpublic int numDimensions()
DoubleNearestNeighboursnumDimensions in class DoubleNearestNeighbourspublic int size()
NearestNeighbourspublic void searchKNN(double[][] qus, int K, int[][] argmins, double[][] mins)
NearestNeighboursFor 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
qus - An array of N query vectorsK - the number of neighbours to findargmins - 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.public void searchNN(double[][] qus, int[] argmins, double[] mins)
NearestNeighboursFor 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
qus - An array of N query vectorsargmins - 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.public void searchKNN(List<double[]> qus, int K, int[][] argmins, double[][] mins)
NearestNeighboursFor 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
qus - An array of N query vectorsK - the number of neighbours to findargmins - 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.public void searchNN(List<double[]> qus, int[] argmins, double[] mins)
NearestNeighboursFor 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
qus - An array of N query vectorsargmins - 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.public List<IntDoublePair> searchKNN(double[] query, int K)
NearestNeighboursIf k neighbours cannot be determined, then the resultant list might have fewer than k elements.
query - the query vectorK - the number of neighbours to search forpublic IntDoublePair searchNN(double[] query)
NearestNeighbours
If the nearest-neighbour cannot be determined null will be
returned.
query - the query vector