edu.wlu.cs.levy.CG
Class KDTree<T>

java.lang.Object
  extended by edu.wlu.cs.levy.CG.KDTree<T>

public class KDTree<T>
extends java.lang.Object

KDTree is a class supporting KD-tree insertion, deletion, equality search, range search, and nearest neighbor(s) using double-precision floating-point keys. Splitting dimension is chosen naively, by depth modulo K. Semantics are as follows:

Implements the Nearest Neighbor algorithm (Table 6.4) of
 @techreport{AndrewMooreNearestNeighbor,
   author  = {Andrew Moore},
   title   = {An introductory tutorial on kd-trees},
   institution = {Robotics Institute, Carnegie Mellon University},
   year    = {1991},
   number  = {Technical Report No. 209, Computer Laboratory, 
              University of Cambridge},
   address = {Pittsburgh, PA}
 }
 

Since:
JDK1.2

Constructor Summary
KDTree(int k)
          Creates a KD-tree with specified number of dimensions.
KDTree(int k, long timeout)
           
 
Method Summary
 void delete(double[] key)
           
 void delete(double[] key, boolean optional)
          Delete a node from a KD-tree.
 void edit(double[] key, edu.wlu.cs.levy.CG.Editor<T> editor)
          Edit a node in a KD-tree
 void insert(double[] key, T value)
          Insert a node in a KD-tree.
 T nearest(double[] key)
          Find KD-tree node whose key is nearest neighbor to key.
 java.util.List<T> nearest(double[] key, int n)
          Find KD-tree nodes whose keys are n nearest neighbors to key.
 java.util.List<T> nearest(double[] key, int n, edu.wlu.cs.levy.CG.Checker<T> checker)
          Find KD-tree nodes whose keys are n nearest neighbors to key.
 java.util.List<T> nearestEuclidean(double[] key, double dist)
          Find KD-tree nodes whose keys are within a given Euclidean distance of a given key.
 java.util.List<T> nearestHamming(double[] key, double dist)
          Find KD-tree nodes whose keys are within a given Hamming distance of a given key.
 java.util.List<T> range(double[] lowk, double[] uppk)
          Range search in a KD-tree.
 T search(double[] key)
          Find KD-tree node whose key is identical to key.
 int size()
           
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

KDTree

public KDTree(int k)
Creates a KD-tree with specified number of dimensions.

Parameters:
k - number of dimensions

KDTree

public KDTree(int k,
              long timeout)
Method Detail

insert

public void insert(double[] key,
                   T value)
            throws KeySizeException,
                   KeyDuplicateException
Insert a node in a KD-tree. Uses algorithm translated from 352.ins.c of
   @Book{GonnetBaezaYates1991,                                   
     author =    {G.H. Gonnet and R. Baeza-Yates},
     title =     {Handbook of Algorithms and Data Structures},
     publisher = {Addison-Wesley},
     year =      {1991}
   }
   

Parameters:
key - key for KD-tree node
value - value at that key
Throws:
KeySizeException - if key.length mismatches K
KeyDuplicateException - if key already in tree

edit

public void edit(double[] key,
                 edu.wlu.cs.levy.CG.Editor<T> editor)
          throws KeySizeException,
                 KeyDuplicateException
Edit a node in a KD-tree

Parameters:
key - key for KD-tree node
editor - object to edit the value at that key
Throws:
KeySizeException - if key.length mismatches K
KeyDuplicateException - if key already in tree

search

public T search(double[] key)
         throws KeySizeException
Find KD-tree node whose key is identical to key. Uses algorithm translated from 352.srch.c of Gonnet & Baeza-Yates.

Parameters:
key - key for KD-tree node
Returns:
object at key, or null if not found
Throws:
KeySizeException - if key.length mismatches K

delete

public void delete(double[] key)
            throws KeySizeException,
                   KeyMissingException
Throws:
KeySizeException
KeyMissingException

delete

public void delete(double[] key,
                   boolean optional)
            throws KeySizeException,
                   KeyMissingException
Delete a node from a KD-tree. Instead of actually deleting node and rebuilding tree, marks node as deleted. Hence, it is up to the caller to rebuild the tree as needed for efficiency.

Parameters:
key - key for KD-tree node
optional - if false and node not found, throw an exception
Throws:
KeySizeException - if key.length mismatches K
KeyMissingException - if no node in tree has key

nearest

public T nearest(double[] key)
          throws KeySizeException
Find KD-tree node whose key is nearest neighbor to key.

Parameters:
key - key for KD-tree node
Returns:
object at node nearest to key, or null on failure
Throws:
KeySizeException - if key.length mismatches K

nearest

public java.util.List<T> nearest(double[] key,
                                 int n)
                          throws KeySizeException,
                                 java.lang.IllegalArgumentException
Find KD-tree nodes whose keys are n nearest neighbors to key.

Parameters:
key - key for KD-tree node
n - number of nodes to return
Returns:
objects at nodes nearest to key, or null on failure
Throws:
KeySizeException - if key.length mismatches K
java.lang.IllegalArgumentException

nearestEuclidean

public java.util.List<T> nearestEuclidean(double[] key,
                                          double dist)
                                   throws KeySizeException
Find KD-tree nodes whose keys are within a given Euclidean distance of a given key.

Parameters:
key - key for KD-tree node
d - Euclidean distance
Returns:
objects at nodes with distance of key, or null on failure
Throws:
KeySizeException - if key.length mismatches K

nearestHamming

public java.util.List<T> nearestHamming(double[] key,
                                        double dist)
                                 throws KeySizeException
Find KD-tree nodes whose keys are within a given Hamming distance of a given key.

Parameters:
key - key for KD-tree node
d - Hamming distance
Returns:
objects at nodes with distance of key, or null on failure
Throws:
KeySizeException - if key.length mismatches K

nearest

public java.util.List<T> nearest(double[] key,
                                 int n,
                                 edu.wlu.cs.levy.CG.Checker<T> checker)
                          throws KeySizeException,
                                 java.lang.IllegalArgumentException
Find KD-tree nodes whose keys are n nearest neighbors to key. Uses algorithm above. Neighbors are returned in ascending order of distance to key.

Parameters:
key - key for KD-tree node
n - how many neighbors to find
checker - an optional object to filter matches
Returns:
objects at node nearest to key, or null on failure
Throws:
KeySizeException - if key.length mismatches K
java.lang.IllegalArgumentException - if n is negative or exceeds tree size

range

public java.util.List<T> range(double[] lowk,
                               double[] uppk)
                        throws KeySizeException
Range search in a KD-tree. Uses algorithm translated from 352.range.c of Gonnet & Baeza-Yates.

Parameters:
lowk - lower-bounds for key
uppk - upper-bounds for key
Returns:
array of Objects whose keys fall in range [lowk,uppk]
Throws:
KeySizeException - on mismatch among lowk.length, uppk.length, or K

size

public int size()

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object