moa.clusterers.outliers.utils.mtree

Class MTree<DATA>

java.lang.Object

moa.clusterers.outliers.utils.mtree.MTree<DATA>

Type Parameters:

DATA - The type of data that will be indexed by the M-Tree. Objects of this type are stored in HashMaps and HashSets, so their hashCode() and equals() methods must be consistent.

public class MTree<DATA>
extends Object

The main class that implements the M-Tree.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	MTree.Query An Iterable class which can be iterated to fetch the results of a nearest-neighbors query.
class	MTree.ResultItem The type of the results for nearest-neighbor queries.

Field Summary

Fields

Modifier and Type	Field and Description
static int	DEFAULT_MIN_NODE_CAPACITY The default minimum capacity of nodes in an M-Tree, when not specified in the constructor call.
protected DistanceFunction<? super DATA>	distanceFunction
protected int	maxNodeCapacity
protected int	minNodeCapacity
protected moa.clusterers.outliers.utils.mtree.MTree.Node	root
protected SplitFunction<DATA>	splitFunction

Constructor Summary

Constructors

Constructor and Description
MTree(DistanceFunction<? super DATA> distanceFunction, SplitFunction<DATA> splitFunction) Constructs an M-Tree with the specified distance function.
MTree(int minNodeCapacity, DistanceFunction<? super DATA> distanceFunction, SplitFunction<DATA> splitFunction) Constructs an M-Tree with the specified minimum node capacity and distance function.
MTree(int minNodeCapacity, int maxNodeCapacity, DistanceFunction<? super DATA> distanceFunction, SplitFunction<DATA> splitFunction) Constructs an M-Tree with the specified minimum and maximum node capacities and distance function.

Method Summary

Methods

Modifier and Type	Method and Description
protected void	_check()
void	add(DATA data) Adds and indexes a data object.
MTree.Query	getNearest(DATA queryData) Performs a nearest-neighbor query on the M-Tree, without constraints.
MTree.Query	getNearest(DATA queryData, double range, int limit) Performs a nearest-neighbor query on the M-Tree, constrained by distance and/or the number of neighbors.
MTree.Query	getNearestByLimit(DATA queryData, int limit) Performs a nearest-neighbors query on the M-Tree, constrained by the number of neighbors.
MTree.Query	getNearestByRange(DATA queryData, double range) Performs a nearest-neighbors query on the M-Tree, constrained by distance.
boolean	remove(DATA data) Removes a data object from the M-Tree.

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_MIN_NODE_CAPACITY

public static final int DEFAULT_MIN_NODE_CAPACITY

The default minimum capacity of nodes in an M-Tree, when not specified in the constructor call.

See Also:

Constant Field Values

minNodeCapacity

protected int minNodeCapacity

maxNodeCapacity

protected int maxNodeCapacity

distanceFunction

protected DistanceFunction<? super DATA> distanceFunction

splitFunction

protected SplitFunction<DATA> splitFunction

root

protected moa.clusterers.outliers.utils.mtree.MTree.Node root

Constructor Detail

MTree

public MTree(DistanceFunction<? super DATA> distanceFunction,
     SplitFunction<DATA> splitFunction)

Constructs an M-Tree with the specified distance function.

Parameters:

distanceFunction - The object used to calculate the distance between two data objects.

MTree

public MTree(int minNodeCapacity,
     DistanceFunction<? super DATA> distanceFunction,
     SplitFunction<DATA> splitFunction)

Constructs an M-Tree with the specified minimum node capacity and distance function.

Parameters:

minNodeCapacity - The minimum capacity for the nodes of the tree.

distanceFunction - The object used to calculate the distance between two data objects.

splitFunction - The object used to process the split of nodes if they are full when a new child must be added.

MTree

public MTree(int minNodeCapacity,
     int maxNodeCapacity,
     DistanceFunction<? super DATA> distanceFunction,
     SplitFunction<DATA> splitFunction)

Constructs an M-Tree with the specified minimum and maximum node capacities and distance function.

Parameters:

minNodeCapacity - The minimum capacity for the nodes of the tree.

maxNodeCapacity - The maximum capacity for the nodes of the tree.

distanceFunction - The object used to calculate the distance between two data objects.

splitFunction - The object used to process the split of nodes if they are full when a new child must be added.

Method Detail

add

public void add(DATA data)

Adds and indexes a data object.

An object that is already indexed should not be added. There is no validation regarding this, and the behavior is undefined if done.

Parameters:

data - The data object to index.

remove

public boolean remove(DATA data)

Removes a data object from the M-Tree.

Parameters:

data - The data object to be removed.

Returns:

true if and only if the object was found.

getNearestByRange

public MTree.Query getNearestByRange(DATA queryData,
                            double range)

Performs a nearest-neighbors query on the M-Tree, constrained by distance.

Parameters:

queryData - The query data object.

range - The maximum distance from queryData to fetched neighbors.

Returns:

A MTree.Query object used to iterate on the results.

getNearestByLimit

public MTree.Query getNearestByLimit(DATA queryData,
                            int limit)

Performs a nearest-neighbors query on the M-Tree, constrained by the number of neighbors.

Parameters:

queryData - The query data object.

limit - The maximum number of neighbors to fetch.

Returns:

A MTree.Query object used to iterate on the results.

getNearest

public MTree.Query getNearest(DATA queryData,
                     double range,
                     int limit)

Performs a nearest-neighbor query on the M-Tree, constrained by distance and/or the number of neighbors.

Parameters:

queryData - The query data object.

range - The maximum distance from queryData to fetched neighbors.

limit - The maximum number of neighbors to fetch.

Returns:

A MTree.Query object used to iterate on the results.

getNearest

public MTree.Query getNearest(DATA queryData)

Performs a nearest-neighbor query on the M-Tree, without constraints.

Parameters:

queryData - The query data object.

Returns:

A MTree.Query object used to iterate on the results.

_check

protected void _check()