weka.core.neighboursearch.kdtrees

Class MedianOfWidestDimension

java.lang.Object

weka.core.neighboursearch.kdtrees.KDTreeNodeSplitter

weka.core.neighboursearch.kdtrees.MedianOfWidestDimension

All Implemented Interfaces:

java.io.Serializable, OptionHandler, RevisionHandler, TechnicalInformationHandler

public class MedianOfWidestDimension
extends KDTreeNodeSplitter
implements TechnicalInformationHandler

The class that splits a KDTree node based on the median value of a dimension in which the node's points have the widest spread.

For more information see also:

Jerome H. Friedman, Jon Luis Bentley, Raphael Ari Finkel (1977). An Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Transactions on Mathematics Software. 3(3):209-226.

BibTeX:

 @article{Friedman1977,
    author = {Jerome H. Friedman and Jon Luis Bentley and Raphael Ari Finkel},
    journal = {ACM Transactions on Mathematics Software},
    month = {September},
    number = {3},
    pages = {209-226},
    title = {An Algorithm for Finding Best Matches in Logarithmic Expected Time},
    volume = {3},
    year = {1977}
 }
 

Version:

$Revision: 1.2 $

Author:

Ashraf M. Kibriya (amk14[at-the-rate]cs[dot]waikato[dot]ac[dot]nz)

See Also:

Serialized Form

Field Summary

Fields inherited from class weka.core.neighboursearch.kdtrees.KDTreeNodeSplitter

MAX, MIN, WIDTH

Constructor Summary

Constructors

Constructor and Description
MedianOfWidestDimension()

Method Summary

Modifier and Type	Method and Description
java.lang.String	getRevision() Returns the revision string.
TechnicalInformation	getTechnicalInformation() Returns an instance of a TechnicalInformation object, containing detailed information about the technical background of this class, e.g., paper reference or book this class is based on.
java.lang.String	globalInfo() Returns a string describing this nearest neighbour search algorithm.
int	select(int attIdx, int[] indices, int left, int right, int k) Implements computation of the kth-smallest element according to Manber's "Introduction to Algorithms".
void	splitNode(KDTreeNode node, int numNodesCreated, double[][] nodeRanges, double[][] universe) Splits a node into two based on the median value of the dimension in which the points have the widest spread.

Methods inherited from class weka.core.neighboursearch.kdtrees.KDTreeNodeSplitter

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

Methods inherited from class java.lang.Object

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

Constructor Detail

MedianOfWidestDimension

public MedianOfWidestDimension()

Method Detail

globalInfo

public java.lang.String globalInfo()

Returns a string describing this nearest neighbour search algorithm.

Returns:

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

getTechnicalInformation

public TechnicalInformation getTechnicalInformation()

Returns an instance of a TechnicalInformation object, containing detailed information about the technical background of this class, e.g., paper reference or book this class is based on.

Specified by:

getTechnicalInformation in interface TechnicalInformationHandler

Returns:

the technical information about this class

splitNode

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

Splits a node into two based on the median value of the dimension in which the points have the widest spread. After splitting two new nodes are created and 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:

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

select

public int select(int attIdx,
                  int[] indices,
                  int left,
                  int right,
                  int k)

Implements computation of the kth-smallest element according to Manber's "Introduction to Algorithms".

Parameters:

attIdx - The dimension/attribute of the instances in which to find the kth-smallest element.

indices - The master index array containing indices of the instances.

left - The begining index of the portion of the master index array in which to find the kth-smallest element.

right - The end index of the portion of the master index array in which to find the kth-smallest element.

k - The value of k

Returns:

The index of the kth-smallest element

getRevision

public java.lang.String getRevision()

Returns the revision string.

Specified by:

getRevision in interface RevisionHandler

Overrides:

getRevision in class KDTreeNodeSplitter

Returns:

the revision