com.rapidminer.tools.math.container
Class KDTree<T extends java.io.Serializable>

java.lang.Object
  com.rapidminer.tools.math.container.KDTree<T>

Type Parameters:

T - This is the type of value with is stored with the points and retrieved on nearest neighbour search

All Implemented Interfaces:

GeometricDataCollection<T>, java.io.Serializable, java.lang.Iterable<T>

public class KDTree<T extends java.io.Serializable>
extends java.lang.Object
implements GeometricDataCollection<T>

This class is an implementation of a KD-Tree for organizing multidimensional datapoints in a fashion supporting the search for nearest neighbours. This is only working well in low dimensions.

Author:

Sebastian Land

See Also:

Serialized Form

Constructor Summary

KDTree(int numberOfDimensions, DistanceMeasure distance)

Method Summary

void	add(double[] values, T storeValue) This method has to be called in order to insert new values into the data structure
T	get(int index) This returns the index-th value added to this collection.
java.util.Collection<Tupel<java.lang.Double,T>>	getNearestValueDistances(double withinDistance, double[] values) This method returns a collection of data from all sample points inside the specified distance.
java.util.Collection<Tupel<java.lang.Double,T>>	getNearestValueDistances(double withinDistance, int butAtLeastK, double[] values) This method returns a collection of data from all sample points inside the specified distance but at least k points.
java.util.Collection<Tupel<java.lang.Double,T>>	getNearestValueDistances(int k, double[] values) This method returns a collection of data from the k nearest sample points.
java.util.Collection<T>	getNearestValues(int k, double[] values) This method returns a collection of the stored data values from the k nearest sample points.
java.util.Iterator<T>	iterator()
int	size() This method has to return the number of stored data points.

Methods inherited from class java.lang.Object

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

Constructor Detail

KDTree

public KDTree(int numberOfDimensions,
              DistanceMeasure distance)

Method Detail

add

public void add(double[] values,
                T storeValue)

Description copied from interface: GeometricDataCollection

This method has to be called in order to insert new values into the data structure

Specified by:

add in interface GeometricDataCollection<T extends java.io.Serializable>

Parameters:

values - specifies the geometric coordinates in data space

storeValue - specifies the value at the given point

getNearestValues

public java.util.Collection<T> getNearestValues(int k,
                                                double[] values)

Description copied from interface: GeometricDataCollection

This method returns a collection of the stored data values from the k nearest sample points.

Specified by:

getNearestValues in interface GeometricDataCollection<T extends java.io.Serializable>

Parameters:

k - the number of neighbours

values - the coordinate of the querry point in the sample dimension

getNearestValueDistances

public java.util.Collection<Tupel<java.lang.Double,T>> getNearestValueDistances(int k,
                                                                                double[] values)

Description copied from interface: GeometricDataCollection

This method returns a collection of data from the k nearest sample points. This collection consists of Tupels containing the distance from querrypoint to the samplepoint and in the second component the contained value of the sample point.

Specified by:

getNearestValueDistances in interface GeometricDataCollection<T extends java.io.Serializable>

Parameters:

k - the number of neighbours

values - the coordinate of the querry point in the sample dimension

getNearestValueDistances

public java.util.Collection<Tupel<java.lang.Double,T>> getNearestValueDistances(double withinDistance,
                                                                                double[] values)

Description copied from interface: GeometricDataCollection

This method returns a collection of data from all sample points inside the specified distance. This collection consists of Tupels containing the distance from querrypoint to the samplepoint and in the second component the contained value of the sample point.

Specified by:

getNearestValueDistances in interface GeometricDataCollection<T extends java.io.Serializable>

values - the coordinate of the querry point in the sample dimension

getNearestValueDistances

public java.util.Collection<Tupel<java.lang.Double,T>> getNearestValueDistances(double withinDistance,
                                                                                int butAtLeastK,
                                                                                double[] values)

Description copied from interface: GeometricDataCollection

This method returns a collection of data from all sample points inside the specified distance but at least k points. So the distance might be enlarged if density is to low. This collection consists of Tupels containing the distance from querrypoint to the samplepoint and in the second component the contained value of the sample point.

Specified by:

getNearestValueDistances in interface GeometricDataCollection<T extends java.io.Serializable>

values - the coordinate of the querry point in the sample dimension

size

public int size()

Description copied from interface: GeometricDataCollection

This method has to return the number of stored data points.

Specified by:

size in interface GeometricDataCollection<T extends java.io.Serializable>

get

public T get(int index)

Description copied from interface: GeometricDataCollection

This returns the index-th value added to this collection.

Specified by:

get in interface GeometricDataCollection<T extends java.io.Serializable>

iterator

public java.util.Iterator<T> iterator()

Specified by:

iterator in interface java.lang.Iterable<T extends java.io.Serializable>