moa.classifiers.lazy.neighboursearch.kdtrees

Class SlidingMidPointOfWidestSide

java.lang.Object

moa.classifiers.lazy.neighboursearch.kdtrees.KDTreeNodeSplitter

moa.classifiers.lazy.neighboursearch.kdtrees.SlidingMidPointOfWidestSide

All Implemented Interfaces:

Serializable

public class SlidingMidPointOfWidestSide
extends KDTreeNodeSplitter

The class that splits a node into two based on the midpoint value of the dimension in which the node's rectangle is widest. If after splitting one side is empty then it is slided towards the non-empty side until there is at least one point on the empty side.

For more information see also:

David M. Mount (2006). ANN Programming Manual. College Park, MD, USA.

BibTeX:

 @manual{Mount2006,
    address = {College Park, MD, USA},
    author = {David M. Mount},
    organization = {Department of Computer Science, University of Maryland},
    title = {ANN Programming Manual},
    year = {2006},
    HTTP = {Available from http://www.cs.umd.edu/\~mount/ANN/}
 }
 

Version:

$Revision: 8034 $

Author:

Ashraf M. Kibriya (amk14@waikato.ac.nz)

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
protected static double	ERR The floating point error to tolerate in finding the widest rectangular side.

Fields inherited from class moa.classifiers.lazy.neighboursearch.kdtrees.KDTreeNodeSplitter

m_EuclideanDistance, m_Instances, m_InstList, m_NormalizeNodeWidth, MAX, MIN, WIDTH

Constructor Summary

Constructors

Constructor and Description
SlidingMidPointOfWidestSide()

Method Summary

Methods

Modifier and Type	Method and Description
String	globalInfo() Returns a string describing this nearest neighbour search algorithm.
protected int	rearrangePoints(int[] indices, int startidx, int endidx, int splitDim, double splitVal) Re-arranges the indices array such that the points <= to the splitVal are on the left of the array and those > the splitVal are on the right.
void	splitNode(KDTreeNode node, int numNodesCreated, double[][] nodeRanges, double[][] universe) Splits a node into two based on the midpoint value of the dimension in which the node's rectangle is widest.

Methods inherited from class moa.classifiers.lazy.neighboursearch.kdtrees.KDTreeNodeSplitter

correctlyInitialized, getOptions, listOptions, setEuclideanDistanceFunction, setInstanceList, setInstances, setNodeWidthNormalization, setOptions, widestDim

Methods inherited from class java.lang.Object

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

Field Detail

ERR

protected static double ERR

The floating point error to tolerate in finding the widest rectangular side.

Constructor Detail

SlidingMidPointOfWidestSide

public SlidingMidPointOfWidestSide()

Method Detail

globalInfo

public String globalInfo()

Returns a string describing this nearest neighbour search algorithm.

Returns:

a description of the algorithm for displaying in the explorer/experimenter gui

splitNode

public void splitNode(KDTreeNode node,
             int numNodesCreated,
             double[][] nodeRanges,
             double[][] universe)
               throws Exception

Splits a node into two based on the midpoint value of the dimension in which the node's rectangle is widest. If after splitting one side is empty then it is slided towards the non-empty side until there is at least one point on the empty side. The two nodes created after the whole splitting are correctly initialised. And, node.left and node.right are set appropriately.

Specified by:

splitNode in class KDTreeNodeSplitter

Parameters:

node - The node to split.

numNodesCreated - The number of nodes that so far have been created for the tree, so that the newly created nodes are assigned correct/meaningful node numbers/ids.

nodeRanges - The attributes' range for the points inside the node that is to be split.

universe - The attributes' range for the whole point-space.

Throws:

Exception - If there is some problem in splitting the given node.

rearrangePoints

protected int rearrangePoints(int[] indices,
                  int startidx,
                  int endidx,
                  int splitDim,
                  double splitVal)

Re-arranges the indices array such that the points <= to the splitVal are on the left of the array and those > the splitVal are on the right.

Parameters:

indices - The master index array.

startidx - The begining index of portion of indices that needs re-arranging.

endidx - The end index of portion of indices that needs re-arranging.

splitDim - The split dimension/attribute.

splitVal - The split value.

Returns:

The startIdx of the points > the splitVal (the points belonging to the right child of the node).