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

java.lang.Object
  extended by 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


Copyright, 2003 - 2010. All rights reserved.
University of Konstanz, Germany.
Chair for Bioinformatics and Information Mining, Prof. Dr. Michael R. Berthold.
You may not modify, publish, transmit, transfer or sell, reproduce, create derivative works from, distribute, perform, display, or in any way exploit any of the content, in whole or in part, except as otherwise expressly permitted in writing by the copyright owner or as specified in the license file distributed with this product.