org.knime.base.util.kdtree
Class KDTree<T>

java.lang.Object
  org.knime.base.util.kdtree.KDTree<T>

Type Parameters:

T - the type of the data that is to be stored in the tree

public class KDTree<T>
extends Object

This class is an implementation of a k-d tree as described in

Friedman, Jerome H; Bentley, Jon Louis; Finkel, Raphael Ari: An Algorithm for Finding Best Matches in Logarithmic Expected Time; ACM Transactions on Mathematical Software; 1997, 3(3), pages 209-226

For creating a k-d tree use the KDTreeBuilder.

Author:

Thorsten Meinl, University of Konstanz

Constructor Summary

KDTree(int k, Node rootNode, int size)
Creates a new optimized k-d tree.

Method Summary

List<NearestNeighbour<T>>	getKNearestNeighbours(double[] query, int k) Searches for the k nearest neighbours of the query pattern.
List<NearestNeighbour<T>>	getMaxDistanceNeighbours(double[] query, double maxDist) Searches for all neighbours of the query pattern that are not more than maxDist away from it.
int	getTestedPatterns() Returns the number of tested patterns during the last call to getKNearestNeighbours(double[], int).
int	size() Returns the tree's size, i.e.

Methods inherited from class java.lang.Object

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

Constructor Detail

KDTree

KDTree(int k,
       Node rootNode,
       int size)

Creates a new optimized k-d tree. This constructor is called by the KDTreeBuilder.

Parameters:

k - the number of dimensions of the patterns

rootNode - the root node of the tree

size - the size of the tree

Method Detail

size

public int size()

Returns the tree's size, i.e. the number of stored patterns. The number of nodes inside the tree is approximately twice the size.

Returns:

the tree's size

getKNearestNeighbours

public List<NearestNeighbour<T>> getKNearestNeighbours(double[] query,
                                                       int k)

Searches for the k nearest neighbours of the query pattern. The returned list is sorted by the distance to the query pattern in increasing order. The returned list may contain more than k patterns if the patterns from k to the end have equal distance to the query pattern.

Parameters:

query - the query pattern, must have the same dimensionality as the patterns inside the tree

k - the number of nearest neighbours to retrieve

Returns:

a sorted list of the nearest neighbours

getMaxDistanceNeighbours

public List<NearestNeighbour<T>> getMaxDistanceNeighbours(double[] query,
                                                          double maxDist)

Searches for all neighbours of the query pattern that are not more than maxDist away from it. The returned list is sorted by the distance to the query pattern in increasing order.

Parameters:

query - the query pattern, must have the same dimensionality as the patterns inside the tree

maxDist - the maximum distance the patterns may have (exclusive)

Returns:

a sorted list of the neighbours

getTestedPatterns

public int getTestedPatterns()

Returns the number of tested patterns during the last call to getKNearestNeighbours(double[], int). The lower the number the better the k-d tree could prune the search.

Returns:

the number of tested patterns