public class MedianOfWidestDimension extends KDTreeNodeSplitter implements TechnicalInformationHandler
@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}
}
MAX, MIN, WIDTH| Constructor and Description |
|---|
MedianOfWidestDimension() |
| 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.
|
getOptions, listOptions, setEuclideanDistanceFunction, setInstanceList, setInstances, setNodeWidthNormalization, setOptionspublic java.lang.String globalInfo()
public TechnicalInformation getTechnicalInformation()
getTechnicalInformation in interface TechnicalInformationHandlerpublic void splitNode(KDTreeNode node, int numNodesCreated, double[][] nodeRanges, double[][] universe) throws java.lang.Exception
splitNode in class KDTreeNodeSplitternode - 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.java.lang.Exception - If there is some problem in splitting the
given node.public int select(int attIdx,
int[] indices,
int left,
int right,
int k)
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 kpublic java.lang.String getRevision()
getRevision in interface RevisionHandlergetRevision in class KDTreeNodeSplitter