org.ddogleg.nn.alg

Class KdTreeSearchBestBinFirst

java.lang.Object

org.ddogleg.nn.alg.KdTreeSearchBestBinFirst

Direct Known Subclasses:

KdTreeSearch1Bbf, KdTreeSearchNBbf

public abstract class KdTreeSearchBestBinFirst
extends java.lang.Object

Approximate search for K-D Trees using the best-bin-first method [1] that supports multiple trees. A priority queue is created where nodes that are more likely to contain points close to the target are given higher priority. It is approximate since only predetermined number of nodes are considered.

Searches are initialized by searching each tree at least once down to a leaf. As these searches are performed, unexplored regions are added to the priority queue. Searching multiple trees is in response to [2], which proposes using a set of random trees to improve search performance and take better advantage of structure found in the data.

[1] Beis, Jeffrey S. and Lowe, David G, "Shape Indexing Using Approximate Nearest-Neighbour Search in High-Dimensional Spaces" CVPR 1997
[2] Silpa-Anan, C. and Hartley, R. "Optimised KD-trees for fast image descriptor matching" CVPR 2008

Constructor Summary

Constructors

Constructor and Description
KdTreeSearchBestBinFirst(int maxNodesSearched) Configures the search

Method Summary

Modifier and Type	Method and Description
void	_findClosest(double[] target)
void	setMaxDistance(double maxDistance)
void	setTree(KdTree tree)
void	setTrees(KdTree[] trees)

Methods inherited from class java.lang.Object

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

Constructor Detail

KdTreeSearchBestBinFirst

public KdTreeSearchBestBinFirst(int maxNodesSearched)

Configures the search

Parameters:

maxNodesSearched - Maximum number of nodes it will search. Used to limit CPU time.

Method Detail

setTree

public void setTree(KdTree tree)

setTrees

public void setTrees(KdTree[] trees)

setMaxDistance

public void setMaxDistance(double maxDistance)

_findClosest

public void _findClosest(double[] target)