org.ai_heuristic.tree

Class KD_TreeNode

java.lang.Object

org.ai_heuristic.tree.TreeNode

org.ai_heuristic.tree.KD_TreeNode

Direct Known Subclasses:

KD_Tree

public class KD_TreeNode
extends TreeNode

This still produces a approximate search result, intended to be optimised by a kd-tree structure. This class can be used as a node in a kd-tree structure, that is a k-dimensional tree structure that allows for faster searches over a limited number of dimensions.

The Value element of the TreeNode is cast to an double[] in this class, where each list object is a dimension key value. So the structure is a MetricDataset storing one or more MetricValues that each store a double[]. This is also the internal conversion if a list of double[] is input, for example. You can use the addChildNode method on the root tree to add the nodes to the structure.

Author:

Kieran Greer

Field Summary

Fields

Modifier and Type	Field and Description
protected int	bucketSize Tree node capacity, or the maximum number of child nodes in a parent node
protected FunctionMetric	evaluator For comparing tree values.
protected EvaluateMathDef	mathCompare Single value math comparisons - simple type
protected NodeStats	nodeStats Some value stats for the nodes

Fields inherited from class org.ai_heuristic.tree.TreeNode

childNodeKeys, childNodes, count, name, parent, value, valueType

Constructor Summary

Constructors

Constructor and Description
KD_TreeNode(int theBucketSize, java.lang.String theValueType, FunctionMetric metricEval, EvaluateMathDef mathEval) Create a new instance of KD_TreeNode.
KD_TreeNode(int theBucketSize, java.lang.String theValueType, MetricDataset theValueList, FunctionMetric metricEval, EvaluateMathDef mathEval) Create a new instance of KD_TreeNode.
KD_TreeNode(java.lang.String theName, int theBucketSize, java.lang.String theValueType, FunctionMetric metricEval, EvaluateMathDef mathEval) Create a new instance of KD_TreeNode.
KD_TreeNode(java.lang.String theName, int theBucketSize, java.lang.String theValueType, MetricDataset theValueList, FunctionMetric metricEval, EvaluateMathDef mathEval) Create a new instance of KD_TreeNode.

Method Summary

Modifier and Type	Method and Description
protected boolean	addToTree(KD_TreeNode treeNode, KD_TreeNode levelNode, int level) Add the node to the tree.
java.lang.Object	clone() Clone and return a copy of this object.
protected int	getBestMatchIndex(java.lang.Object treeValue, KD_TreeNode dimNode, int dim) Get the best position to insert the new node in the current list.
protected KD_TreeNode	getBestMatchNode(java.lang.Object treeValue, int level) Get the best matching node from the child node list, with the following rules: 1.
int	getBucketSize() Get the bucket size for this node.
java.lang.String	getMathEvaluatorClass() Get the class type for the math evaluator.
java.lang.String	getMetricEvaluatorClass() Get the class type for the dataset evaluator.
NodeStats	getNodeStats() Get the stat values for this node - min, max, median.
protected <T> void	search(java.lang.String dsNode, MetricDataset dataset, java.util.ArrayList<KD_TreeNode> kClosest, java.util.ArrayList<T> distances, int level, int k) Search the tree and return the k closest matches to the dataset.
void	setBucketSize(int theBucketSize) Set the node bucket size or maximum capacity.
void	setMathEvaluator(EvaluateMathDef theEvaluator) Set the evaluator for mathematical expressions.
void	setMetricEvaluator(FunctionMetric theEvaluator) Set the evaluator for comparing datasets.
void	setNodeStats(NodeStats theNodeStats) Set the node stats.
protected void	updateNodeStats(java.lang.Object dimValue) Update this node's stats based on the single value for the dimension.

Methods inherited from class org.ai_heuristic.tree.TreeNode

addChildNode, addChildNode, clearChildNodes, getChildNode, getChildNodeDeep, getChildNodeKeys, getChildNodes, getChildNodeValue, getChildNodeValueDeep, getCount, getName, getParent, getValue, getValueType, getValueTypeMD, hasChildNode, hasChildNodeDeep, hasChildNodes, hasChildNodeValue, hasChildNodeValueDeep, hasValue, isLeaf, maxDepth, nodesAtLevel, removeChildNode, setChildNodes, setChildNodes, setCount, setParent, setValue, toString, toString, treeValueDeep

Methods inherited from class java.lang.Object

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

Field Detail

bucketSize

protected int bucketSize

Tree node capacity, or the maximum number of child nodes in a parent node

nodeStats

protected NodeStats nodeStats

Some value stats for the nodes

mathCompare

protected EvaluateMathDef mathCompare

Single value math comparisons - simple type

evaluator

protected FunctionMetric evaluator

For comparing tree values.

Constructor Detail

KD_TreeNode

public KD_TreeNode(int theBucketSize,
                   java.lang.String theValueType,
                   FunctionMetric metricEval,
                   EvaluateMathDef mathEval)
            throws java.lang.Exception

Create a new instance of KD_TreeNode. The name is assigned a unique value.

Parameters:

theBucketSize - the tree node capacity.

theValueType - the type of value that this node supports.

metricEval - the evaluation function.

mathEval - for simple math comparisons.

Throws:

java.lang.Exception - any error.

KD_TreeNode

public KD_TreeNode(java.lang.String theName,
                   int theBucketSize,
                   java.lang.String theValueType,
                   FunctionMetric metricEval,
                   EvaluateMathDef mathEval)
            throws java.lang.Exception

Create a new instance of KD_TreeNode.

Parameters:

theName - a unique name or ID for the node.

theBucketSize - the tree node capacity.

theValueType - the type of value that this node supports.

metricEval - the evaluation function.

mathEval - for simple math comparisons.

Throws:

java.lang.Exception - any error.

KD_TreeNode

public KD_TreeNode(int theBucketSize,
                   java.lang.String theValueType,
                   MetricDataset theValueList,
                   FunctionMetric metricEval,
                   EvaluateMathDef mathEval)
            throws java.lang.Exception

Create a new instance of KD_TreeNode. The name is assigned a unique value.

Parameters:

theBucketSize - the tree node capacity.

theValueType - the type of value that this node supports.

theValueList - the list of values for this node.

metricEval - the evaluation function.

mathEval - for simple math comparisons.

Throws:

java.lang.Exception - any error.

KD_TreeNode

public KD_TreeNode(java.lang.String theName,
                   int theBucketSize,
                   java.lang.String theValueType,
                   MetricDataset theValueList,
                   FunctionMetric metricEval,
                   EvaluateMathDef mathEval)
            throws java.lang.Exception

Create a new instance of KD_TreeNode.

Parameters:

theName - a unique name or ID for the node.

theBucketSize - the tree node capacity.

theValueType - the type of value that this node supports.

theValueList - the list of values for this node.

metricEval - the evaluation function.

mathEval - for simple math comparisons.

Throws:

java.lang.Exception - any error.

Method Detail

search

protected <T> void search(java.lang.String dsNode,
                          MetricDataset dataset,
                          java.util.ArrayList<KD_TreeNode> kClosest,
                          java.util.ArrayList<T> distances,
                          int level,
                          int k)
                   throws java.lang.Exception

Search the tree and return the k closest matches to the dataset.

Parameters:

dsNode - name of the node the data belongs to, if already in the tree. This node is not then considered during the search,

dataset - the dataset to compare with, probably from the dataset node.

kClosest - add the k-closest nodes to this list.

distances - list of distances for each stored closest node.

level - the current tree level.

k - the number of matches to return.

Throws:

java.lang.Exception - any error.

addToTree

protected boolean addToTree(KD_TreeNode treeNode,
                            KD_TreeNode levelNode,
                            int level)
                     throws java.lang.Exception

Add the node to the tree.

Parameters:

treeNode - the node with a list of values of size dimSize.

levelNode - the node from the last level to add to.

level - the new tree level.

Returns:

true if added OK, false if not.

Throws:

java.lang.Exception - any error.

getBestMatchNode

protected KD_TreeNode getBestMatchNode(java.lang.Object treeValue,
                                       int level)
                                throws java.lang.Exception

Get the best matching node from the child node list, with the following rules:
1. If stats not set, use the dimension value, where it is the first node with a larger value at this dimension.
2. Otherwise, if inside both min and max stats bounds, then return that node.
3. Otherwise, if less than next node's min value then return current.
4. Otherwise, add to the final node.

Parameters:

treeValue - the value to compare with. A single simple value, not a dataset, which is evaluated using SimpleMathCompare.

level - the level in the tree adding the new node at, +1 from this node.

Returns:

the best matching node.

Throws:

java.lang.Exception - any error.

getBestMatchIndex

protected int getBestMatchIndex(java.lang.Object treeValue,
                                KD_TreeNode dimNode,
                                int dim)
                         throws java.lang.Exception

Get the best position to insert the new node in the current list. That would be before the first node with a larger value at this dimension.

Parameters:

treeValue - the value to use.

dimNode - node that the list belongs to.

dim - dimension in the tree.

Returns:

an index position in the list to insert the new node at.

Throws:

java.lang.Exception - any error.

updateNodeStats

protected void updateNodeStats(java.lang.Object dimValue)
                        throws java.lang.Exception

Update this node's stats based on the single value for the dimension.

Parameters:

dimValue - the dimension value only, not the full n-d list.

Throws:

java.lang.Exception - any error.

setBucketSize

public void setBucketSize(int theBucketSize)

Set the node bucket size or maximum capacity.

Parameters:

theBucketSize - the bucket size.

getBucketSize

public int getBucketSize()

Get the bucket size for this node.

Returns:

the value of bucketSize.

setNodeStats

public void setNodeStats(NodeStats theNodeStats)

Set the node stats.

Parameters:

theNodeStats - the node stats.

getNodeStats

public NodeStats getNodeStats()

Get the stat values for this node - min, max, median.

Returns:

the value of nodeStats.

setMetricEvaluator

public void setMetricEvaluator(FunctionMetric theEvaluator)

Set the evaluator for comparing datasets.

Parameters:

theEvaluator - the evaluator to use.

setMathEvaluator

public void setMathEvaluator(EvaluateMathDef theEvaluator)

Set the evaluator for mathematical expressions.

Parameters:

theEvaluator - the evaluator to use.

getMetricEvaluatorClass

public java.lang.String getMetricEvaluatorClass()

Get the class type for the dataset evaluator.

Returns:

class type of evaluator, or null if one is not loaded.

getMathEvaluatorClass

public java.lang.String getMathEvaluatorClass()

Get the class type for the math evaluator.

Returns:

class type of mathCompare, or null if one is not loaded.

clone

public java.lang.Object clone()

Clone and return a copy of this object. Child nodes are not cloned.

Overrides:

clone in class TreeNode

Returns:

a light copy of this node.