Package org.tribuo.math.neighbour.kdtree
Class KDTree
java.lang.Object
org.tribuo.math.neighbour.kdtree.KDTree
 All Implemented Interfaces:
NeighboursQuery
A kd tree nearest neighbour query implementation.
For the original algorithm see:
J.L. Bentley "Multidimensional Binary Search Trees Used for Associative Searching", Commun. ACM, Vol 18, Sept. 1975, 509–517 Multidimensional Binary Search Trees Used for Associative Searching
Some aspects of this implementation, particularly the logic which finds the median and partitions the points for each dimension, are derived from:
G. Heineman, G. Pollice, and S. Selkow. "Algorithms in a Nutshell" O'Reilly Media, Inc. 2008. Algorithms in a Nutshell

Method Summary
Modifier and TypeMethodDescriptionorg.tribuo.math.neighbour.kdtree.DimensionNode
approximateParentNode
(SGDVector point) This makes a fast approximation of the provided point's parent node, if it were being inserted into the tree.Queries a set ofSGDVector
s to determine the k points nearest to the provided points.Queries a set ofSGDVector
s to determine the k points nearest to the provided point.queryAll
(int k) Queries a set ofSGDVector
s to determine the k points nearest to every point in the set.

Method Details

query
Description copied from interface:NeighboursQuery
Queries a set ofSGDVector
s to determine the k points nearest to the provided point. When there are multiple points equidistant from the provided point, the order in which they are returned may vary depending on the implementation. Specified by:
query
in interfaceNeighboursQuery
 Parameters:
point
 The point to determine the nearest k points for.k
 The number of neighbouring points to identify. Returns:
 A list of k
Pair
s, where a pair contains the index of the neighbouring point in the original data and the distance between this point and the provided point.

query
public List<List<com.oracle.labs.mlrg.olcut.util.Pair<Integer,Double>>> query(SGDVector[] points, int k) Description copied from interface:NeighboursQuery
Queries a set ofSGDVector
s to determine the k points nearest to the provided points. When there are multiple points equidistant from a provided point, the order in which they are returned may vary depending on the implementation. Specified by:
query
in interfaceNeighboursQuery
 Parameters:
points
 An array of points to determine the nearest k points for.k
 The number of neighbouring points to identify. Returns:
 An list containing lists of k
Pair
s. There is list entry for each provided point which is a list of k pairs. Each pair contains the index of the neighbouring point in the original data and the distance between this point and the provided point.

queryAll
Description copied from interface:NeighboursQuery
Queries a set ofSGDVector
s to determine the k points nearest to every point in the set. When there are multiple points equidistant from a point in the set, the order in which they are returned may vary depending on the implementation. Specified by:
queryAll
in interfaceNeighboursQuery
 Parameters:
k
 The number of neighbouring points to identify. Returns:
 A list containing lists of k
Pair
s. There is list entry for each provided point which is a list of k pairs. Each pair contains the index of the neighbouring point in the original data and the distance between this point and the provided point.

approximateParentNode
This makes a fast approximation of the provided point's parent node, if it were being inserted into the tree. Parameters:
point
 The target point. Returns:
 The approximate parent node.
