gov.sandia.cognition.math.geometry

Class KDTree<VectorType extends Vectorizable,DataType,PairType extends Pair<? extends VectorType,DataType>>

java.lang.Object

java.util.AbstractCollection<PairType>

gov.sandia.cognition.math.geometry.KDTree<VectorType,DataType,PairType>

Type Parameters:

VectorType - Type of Vectorizable, the first values

DataType - Type of data in the Pair, the second values

PairType - Type of Pair to use in the KDTree.

All Implemented Interfaces:

CloneableSerializable, java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<PairType>, java.util.Collection<PairType>

@PublicationReference(author="Andrew W. Moore",title="An intoductory tutorial on kd-trees",type=TechnicalReport,publication="University of Cambridge Computer Laboratory Technical Report No. 209",year=1991,url="http://www.autonlab.org/autonweb/14665.html?branch=1&language=2") @PublicationReference(author="Wikipedia",title="kd-tree",type=WebPage,year=2009,url="http://en.wikipedia.org/wiki/Kd-tree")
public class KDTree<VectorType extends Vectorizable,DataType,PairType extends Pair<? extends VectorType,DataType>>
extends java.util.AbstractCollection<PairType>
implements CloneableSerializable

Implementation of a kd-tree. Every node in a KDTree has a k-dimensional Vectorizable point and an associated value as a generic "DataType." The At each depth in the KDTree, the KDTree partitions the Vectorizables into two sets along a particular dimension according to the Vectorizable stored in the node value. The dimension used to partition at a particular depth is (depth % k). Vectorizables with values less than or equal to the node-value-dimension are placed into the left subtree, and those greater than the node-value-dimension are stored into the right subtree. This makes average-case nearest-neighbor lookup into a balanced KDTree with "N" points of O(log(N)), rather than the typical "N" time for linear search. Construction of a balanced KDTree with N points takes average-case O(N log(N)).

Since:

3.0

Author:

Kevin R. Dixon

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	KDTree.InOrderKDTreeIterator<VectorType extends Vectorizable,DataType,PairType extends Pair<? extends VectorType,DataType>> Iterates through the KDTree using "inorder", also known as "symmetric traversal", of the tree.
protected static class	KDTree.Neighborhood<VectorType extends Vectorizable,DataType,PairType extends Pair<? extends VectorType,DataType>> A Collection of nearby pairs.
protected static class	KDTree.PairFirstVectorizableIndexComparator Comparator for Pairs that have a Vectorizable as its first parameter.

Field Summary

Fields

Modifier and Type	Field and Description
protected KDTree.PairFirstVectorizableIndexComparator	comparator Comparator of this node to determine less than, greater than, or equality.
protected KDTree<VectorType,DataType,PairType>	leftChild Left child of this subtree
protected int	num Number of elements in this subtree.
protected KDTree<VectorType,DataType,PairType>	parent Parent of this node of the subtree.
protected KDTree<VectorType,DataType,PairType>	rightChild Right child of this subtree.
protected PairType	value VectorType,DataType value for this node of the subtree.

Constructor Summary

Constructors

Modifier	Constructor and Description
	KDTree() Default constructor
protected	KDTree(java.util.ArrayList<? extends PairType> points, KDTree.PairFirstVectorizableIndexComparator comparator, int dimensionality, KDTree<VectorType,DataType,PairType> parent) Creates a balanced KDTree subtree for recursion purposes from the given ArrayList of points.
	KDTree(java.util.Collection<? extends PairType> points) Creates a balanced KDTree from the given points.
protected	KDTree(PairType value, KDTree.PairFirstVectorizableIndexComparator comparator, KDTree<VectorType,DataType,PairType> parent) Creates a KDTree subtree for recursion purposes.

Method Summary

Modifier and Type	Method and Description
boolean	add(PairType point)
KDTree<VectorType,DataType,PairType>	clone() Creates a new clone (shallow copy) of this object.
protected double	computeMinimumDifference(VectorType key) Computes the minimum absolute difference between the given key and the "first" value stored in this subtree for the index given by the embedded comparator.
static <VectorType extends Vectorizable,DataType,PairType extends Pair<? extends VectorType,DataType>> KDTree<VectorType,DataType,PairType>	createBalanced(java.util.Collection<? extends PairType> points) Creates a balanced KDTree based on the given collection of Pairs.
protected void	findNearest(VectorType key, int k, KDTree.Neighborhood<VectorType,DataType,PairType> neighborhood, Metric<? super VectorType> metric) Finds the "num" nearest neighbors to the given "key" stored in the KDTree.
java.util.Collection<PairType>	findNearest(VectorType key, int k, Metric<? super VectorType> metric) Finds the "num" nearest neighbors to the given "key" stored in the KDTree.
protected void	findNearestWithinRadius(VectorType key, double radius, KDTree.Neighborhood<VectorType,DataType,PairType> neighborhood, Metric<? super VectorType> metric) Finds the neighbors within a given distance to the given "key" stored in the KDTree.
java.util.Collection<PairType>	findNearestWithinRadius(VectorType key, double radius, Metric<? super VectorType> metric) Finds the neighbors within a given distance to the given "key" stored in the KDTree.
java.util.Iterator<PairType>	iterator() Iterates through the KDTree using "inorder", also known as "symmetric traversal", of the tree.
KDTree<VectorType,DataType,PairType>	reblanace() Rebalances the KDTree.
int	size()
java.lang.String	toString()
protected java.lang.String	toString(java.lang.String prefix) Recursively prints out the tree "inorder" by printing out the left subtree, then the node, then the right subtree.

Methods inherited from class java.util.AbstractCollection

addAll, clear, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Collection

equals, hashCode, parallelStream, removeIf, spliterator, stream

Methods inherited from interface java.lang.Iterable

forEach

Field Detail

num

protected int num

Number of elements in this subtree.

value

protected PairType extends Pair<? extends VectorType,DataType> value

VectorType,DataType value for this node of the subtree.

parent

protected KDTree<VectorType extends Vectorizable,DataType,PairType extends Pair<? extends VectorType,DataType>> parent

Parent of this node of the subtree.

leftChild

protected KDTree<VectorType extends Vectorizable,DataType,PairType extends Pair<? extends VectorType,DataType>> leftChild

Left child of this subtree

rightChild

protected KDTree<VectorType extends Vectorizable,DataType,PairType extends Pair<? extends VectorType,DataType>> rightChild

Right child of this subtree.

comparator

protected KDTree.PairFirstVectorizableIndexComparator comparator

Comparator of this node to determine less than, greater than, or equality.

Constructor Detail

KDTree

public KDTree()

Default constructor

KDTree

public KDTree(java.util.Collection<? extends PairType> points)

Creates a balanced KDTree from the given points.

Parameters:

points - Points to load into the KDTree.

KDTree

protected KDTree(PairType value,
                 KDTree.PairFirstVectorizableIndexComparator comparator,
                 KDTree<VectorType,DataType,PairType> parent)

Creates a KDTree subtree for recursion purposes.

Parameters:

value - Value of the head of the subtree.

comparator - Comparator to use for the Vectorizables.

parent - Parent node of this subtree.

KDTree

protected KDTree(java.util.ArrayList<? extends PairType> points,
                 KDTree.PairFirstVectorizableIndexComparator comparator,
                 int dimensionality,
                 KDTree<VectorType,DataType,PairType> parent)

Creates a balanced KDTree subtree for recursion purposes from the given ArrayList of points. This is an O(n log n) operation for "n" points because we use a clever linear-time kth selection algorithm in CollectionUtil.findKthLargest().

Parameters:

points - Points to load into the subtree.

dimensionality - Dimensionality of the Vectorizables.

comparator - Comparator to use for the Vectorizables.

parent - Parent node of this subtree.

Method Detail

clone

public KDTree<VectorType,DataType,PairType> clone()

Description copied from interface: CloneableSerializable

Creates a new clone (shallow copy) of this object.

Specified by:

clone in interface CloneableSerializable

Overrides:

clone in class java.lang.Object

Returns:

A new clone (shallow copy) of this object.

createBalanced

public static <VectorType extends Vectorizable,DataType,PairType extends Pair<? extends VectorType,DataType>> KDTree<VectorType,DataType,PairType> createBalanced(java.util.Collection<? extends PairType> points)

Creates a balanced KDTree based on the given collection of Pairs. This is an O(n log n) operation for "n" points because we use a clever linear-time kth selection algorithm in CollectionUtil.findKthLargest().

Type Parameters:

VectorType - Type of Vectorizable, the first values.

DataType - Type of data in the Pair, the second values.

PairType - Type of Pair to use in the KDTree.

Parameters:

points - Points to load into the tree.

Returns:

Balanced KDTree that contains all the given points.

reblanace

public KDTree<VectorType,DataType,PairType> reblanace()

Rebalances the KDTree. Does not modify this KDTree.

Returns:

Balanced representation of this KDTree.

add

public boolean add(PairType point)

Specified by:

add in interface java.util.Collection<PairType extends Pair<? extends VectorType,DataType>>

Overrides:

add in class java.util.AbstractCollection<PairType extends Pair<? extends VectorType,DataType>>

size

public int size()

Specified by:

size in interface java.util.Collection<PairType extends Pair<? extends VectorType,DataType>>

Specified by:

size in class java.util.AbstractCollection<PairType extends Pair<? extends VectorType,DataType>>

iterator

@PublicationReference(author="Wikipedia",
                      title="Tree traversal",
                      type=WebPage,
                      year=2009,
                      url="http://en.wikipedia.org/wiki/Tree_traversal#Traversal")
public java.util.Iterator<PairType> iterator()

Iterates through the KDTree using "inorder", also known as "symmetric traversal", of the tree. That is, the recursion proceeds as traverse the left subtree, visit the node, traverse the right subtree.

Specified by:

iterator in interface java.lang.Iterable<PairType extends Pair<? extends VectorType,DataType>>

Specified by:

iterator in interface java.util.Collection<PairType extends Pair<? extends VectorType,DataType>>

Specified by:

iterator in class java.util.AbstractCollection<PairType extends Pair<? extends VectorType,DataType>>

Returns:

Inorder iterator of the KDTree.

toString

public java.lang.String toString()

Overrides:

toString in class java.util.AbstractCollection<PairType extends Pair<? extends VectorType,DataType>>

toString

protected java.lang.String toString(java.lang.String prefix)

Recursively prints out the tree "inorder" by printing out the left subtree, then the node, then the right subtree.

Parameters:

prefix - Prefix to tack onto the recursion values.

Returns:

String representation of the KDTree.

findNearest

public java.util.Collection<PairType> findNearest(VectorType key,
                                                  int k,
                                                  Metric<? super VectorType> metric)

Finds the "num" nearest neighbors to the given "key" stored in the KDTree.

Parameters:

key - Vector to find the nearest neighbors of.

k - Number of neighbors to find.

metric - Metric to use to evaluate the nearness of other points.

Returns:

Collection of nearest points to the "key" query. If "num" is greater than or equal to the number of points in the KDTRee, then the KDTree is returned.

findNearest

protected void findNearest(VectorType key,
                           int k,
                           KDTree.Neighborhood<VectorType,DataType,PairType> neighborhood,
                           Metric<? super VectorType> metric)

Finds the "num" nearest neighbors to the given "key" stored in the KDTree.

Parameters:

key - Vector to find the nearest neighbors of.

k - Number of neighbors to find.

neighborhood - PriorityQueue to store the current nearest neighbors.

metric - Metric to use to evaluate the nearness of other points.

findNearestWithinRadius

public java.util.Collection<PairType> findNearestWithinRadius(VectorType key,
                                                              double radius,
                                                              Metric<? super VectorType> metric)

Finds the neighbors within a given distance to the given "key" stored in the KDTree.

Parameters:

key - Vector to find the nearest neighbors of.

radius - Radius of desired neighborhood.

metric - Metric to use to evaluate the nearness of other points.

Returns:

Collection of points within a given distance to the "key" query.

findNearestWithinRadius

protected void findNearestWithinRadius(VectorType key,
                                       double radius,
                                       KDTree.Neighborhood<VectorType,DataType,PairType> neighborhood,
                                       Metric<? super VectorType> metric)

Finds the neighbors within a given distance to the given "key" stored in the KDTree.

Parameters:

key - Vector to find the nearest neighbors of.

radius - Radius of desired neighborhood.

neighborhood - PriorityQueue to store the neighbors.

metric - Metric to use to evaluate the nearness of other points.

computeMinimumDifference

protected double computeMinimumDifference(VectorType key)

Computes the minimum absolute difference between the given key and the "first" value stored in this subtree for the index given by the embedded comparator. That is, the minimum distance "this is done by intersecting the splitting hyperplane with a hypersphere around the search node [key] that has a radius equal to the current nearest distance. Since the hyperplanes are all axis-aligned this is implemented as a simple comparison to see whether the difference between the splitting coordinate and the search point is less than the distance from the search point to the current best."

Parameters:

key - Vector to compare against.

Returns:

Minimum absolute difference for the given index between the key and the first value stored in this subtree.