gov.sandia.cognition.math.geometry
Class KDTree<VectorType extends Vectorizable,DataType,PairType extends Pair<? extends VectorType,DataType>>

java.lang.Object
  extended by java.util.AbstractCollection<PairType>
      extended by 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, Serializable, Cloneable, Iterable<PairType>, Collection<PairType>

@PublicationReferences(references={@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 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
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
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
  KDTree()
          Default constructor
protected KDTree(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(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
 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(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.
 Collection<PairType> findNearest(VectorType key, int k, Metric<? super VectorType> metric)
          Finds the "num" nearest neighbors to the given "key" stored in the KDTree.
 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()
           
 String toString()
           
protected  String toString(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
 

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(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(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 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(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 Collection<PairType extends Pair<? extends VectorType,DataType>>
Overrides:
add in class AbstractCollection<PairType extends Pair<? extends VectorType,DataType>>

size

public int size()
Specified by:
size in interface Collection<PairType extends Pair<? extends VectorType,DataType>>
Specified by:
size in class 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 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 Iterable<PairType extends Pair<? extends VectorType,DataType>>
Specified by:
iterator in interface Collection<PairType extends Pair<? extends VectorType,DataType>>
Specified by:
iterator in class AbstractCollection<PairType extends Pair<? extends VectorType,DataType>>
Returns:
Inorder iterator of the KDTree.

toString

public String toString()
Overrides:
toString in class AbstractCollection<PairType extends Pair<? extends VectorType,DataType>>

toString

protected String toString(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 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.

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.