Package kieker.analysis.generic.clustering.mtree

Class MTree<T>

java.lang.Object
kieker.analysis.generic.clustering.mtree.MTree<T>
Type Parameters:
T - 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<T>
extends java.lang.Object
The main class that implements the M-Tree.
Since:
2.0.0
Author:
Eduardo R. D'Avila -- initial contribution, Reiner Jung

  • Field Summary

    Fields 
    Modifier and Type Field Description
    static int DEFAULT_MIN_NODE_CAPACITY
    The default minimum capacity of nodes in an M-Tree, when not specified in the constructor call.

  • Constructor Summary

    Constructors 
    Constructor Description
    MTree​(int minNodeCapacity, int maxNodeCapacity, IDistanceFunction<? super T> distanceFunction, ISplitFunction<T> existingSplitFunction)
    Constructs an M-Tree with the specified minimum and maximum node capacities and distance function.
    MTree​(int minNodeCapacity, IDistanceFunction<? super T> distanceFunction, ISplitFunction<T> splitFunction)
    Constructs an M-Tree with the specified minimum node capacity and distance function.
    MTree​(IDistanceFunction<? super T> distanceFunction, ISplitFunction<T> splitFunction)
    Constructs an M-Tree with the specified distance function.

  • Method Summary

    Modifier and Type Method Description
    void add​(T data)
    Adds and indexes a data object.
    protected void check()  
    IDistanceFunction<? super T> getDistanceFunction()  
    int getMaxNodeCapacity()  
    int getMinNodeCapacity()  
    Query<T> getNearest​(T queryData)
    Performs a nearest-neighbor query on the M-Tree, without constraints.
    Query<T> getNearest​(T queryData, double range, int limit)
    Performs a nearest-neighbor query on the M-Tree, constrained by distance and/or the number of neighbors.
    Query<T> getNearestByLimit​(T queryData, int limit)
    Performs a nearest-neighbors query on the M-Tree, constrained by the number of neighbors.
    Query<T> getNearestByRange​(T queryData, double range)
    Performs a nearest-neighbors query on the M-Tree, constrained by distance.
    AbstractNode<T> getRoot()  
    ISplitFunction<T> getSplitFunction()  
    boolean remove​(T 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 Details

  • Constructor Details

    • MTree

      public MTree​(IDistanceFunction<? super T> distanceFunction, ISplitFunction<T> splitFunction)
      Constructs an M-Tree with the specified distance function.
      Parameters:
      distanceFunction - The object used to calculate the distance between two data objects.
      splitFunction - split function

    • MTree

      public MTree​(int minNodeCapacity, IDistanceFunction<? super T> distanceFunction, ISplitFunction<T> 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, IDistanceFunction<? super T> distanceFunction, ISplitFunction<T> existingSplitFunction)
      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.
      existingSplitFunction - The object used to process the split of nodes if they are full when a new child must be added.

  • Method Details

    • add

      public void add​(T data) throws InternalErrorException
      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.
      Throws:
      InternalErrorException - on internal error

    • remove

      public boolean remove​(T data) throws InternalErrorException
      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.
      Throws:
      InternalErrorException - on internal error

    • getNearestByRange

      public Query<T> getNearestByRange​(T 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 Query object used to iterate on the results.

    • getNearestByLimit

      public Query<T> getNearestByLimit​(T 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 Query object used to iterate on the results.

    • getNearest

      public Query<T> getNearest​(T 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 Query object used to iterate on the results.

    • getNearest

      public Query<T> getNearest​(T queryData)
      Performs a nearest-neighbor query on the M-Tree, without constraints.
      Parameters:
      queryData - The query data object.
      Returns:
      A Query object used to iterate on the results.

    • getMaxNodeCapacity

      public int getMaxNodeCapacity()

    • getMinNodeCapacity

      public int getMinNodeCapacity()

    • getSplitFunction

      public ISplitFunction<T> getSplitFunction()

    • getDistanceFunction

      public IDistanceFunction<? super T> getDistanceFunction()

    • getRoot

      public AbstractNode<T> getRoot()

    • check

      protected void check()