edu.wlu.cs.levy.CG
Class KDTree

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

public class KDTree
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:

Since:
JDK1.2

Constructor Summary
KDTree(int k)
          Creates a KD-tree with specified number of dimensions.
 
Method Summary
 void delete(double[] key)
          Delete a node from a KD-tree.
 void insert(double[] key, java.lang.Object value)
          Insert a node in a KD-tree.
 java.lang.Object nearest(double[] key)
          Find KD-tree node whose key is nearest neighbor to key.
 java.lang.Object[] nearest(double[] key, int n)
          Find KD-tree nodes whose keys are n nearest neighbors to key.
 java.lang.Object[] range(double[] lowk, double[] uppk)
          Range search in a KD-tree.
 java.lang.Object search(double[] key)
          Find KD-tree node whose key is identical to key.
 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
Method Detail

insert

public void insert(double[] key,
                   java.lang.Object 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

search

public java.lang.Object 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,
                   edu.wlu.cs.levy.CG.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
Throws:
KeySizeException - if key.length mismatches K
KeyMissingException - if no node in tree has key

nearest

public java.lang.Object nearest(double[] key)
                         throws KeySizeException
Find KD-tree node whose key is nearest neighbor to key. 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}
 }
 

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.lang.Object[] nearest(double[] key,
                                  int n)
                           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
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.lang.Object[] 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

toString

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