Package org.ddogleg.nn.alg.searches

Class KdTreeSearchBestBinFirst<P>

java.lang.Object

org.ddogleg.nn.alg.searches.KdTreeSearchBestBinFirst<P>

Direct Known Subclasses:

KdTreeSearch1Bbf, KdTreeSearchNBbf

public abstract class KdTreeSearchBestBinFirst<P>
extends 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

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	KdTreeSearchBestBinFirst.Helper	Contains information on a node

Field Summary

Fields

Modifier and Type	Field	Description
protected double	bestDistanceSq
protected int	maxNodesSearched
protected int	N
protected int	numNodesSearched

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	KdTreeSearchBestBinFirst(KdTreeDistance<P> distance, int maxNodesSearched)	Configures the search

Method Summary

Modifier and Type	Method	Description
void	_findClosest(P target)
protected void	addToQueue(double closestDistanceSq, KdTree.Node node, P target)	Adds a node to the priority queue.
protected abstract boolean	canImprove(double distanceSq)	Checks to see if it is possible for this distance to improve upon the current best
protected abstract void	checkBestDistance(KdTree.Node node, P target)	Checks to see if the current node's point is the closet point found so far
protected void	searchNode(P target, KdTree.Node n)	Traverse a node down to a leaf.
void	setMaxDistance(double maxDistance)
void	setTree(KdTree tree)
void	setTrees(KdTree[] trees)

Methods inherited from class java.lang.Object

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

Field Details

maxNodesSearched

protected int maxNodesSearched

N

protected int N

bestDistanceSq

protected double bestDistanceSq

numNodesSearched

protected int numNodesSearched

Constructor Details

KdTreeSearchBestBinFirst

protected KdTreeSearchBestBinFirst(KdTreeDistance<P> distance,
 int maxNodesSearched)

Configures the search

Parameters:

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

Method Details

setTree

public void setTree(KdTree tree)

setTrees

public void setTrees(KdTree[] trees)

setMaxDistance

public void setMaxDistance(double maxDistance)

_findClosest

public void _findClosest(P target)

searchNode

protected void searchNode(P target,
 KdTree.Node n)

Traverse a node down to a leaf. Unexplored branches are added to the priority queue.

addToQueue

protected void addToQueue(double closestDistanceSq,
 KdTree.Node node,
 P target)

Adds a node to the priority queue.

Parameters:

closestDistanceSq - The closest distance that a point in the region could possibly be target

checkBestDistance

protected abstract void checkBestDistance(KdTree.Node node,
 P target)

Checks to see if the current node's point is the closet point found so far

canImprove

protected abstract boolean canImprove(double distanceSq)

Checks to see if it is possible for this distance to improve upon the current best

Parameters:

distanceSq - The distance being considered

Returns:

true if it can be better or false if not