mtree
Class MTree

java.lang.Object
  extended by messif.algorithms.Algorithm
      extended by mtree.MTree
All Implemented Interfaces:
java.io.Serializable, java.lang.Cloneable, messif.buckets.split.SplittableAlgorithm

public class MTree
extends messif.algorithms.Algorithm
implements java.io.Serializable, messif.buckets.split.SplittableAlgorithm, java.lang.Cloneable

See Also:
Serialized Form

Nested Class Summary
 
Nested classes/interfaces inherited from class messif.algorithms.Algorithm
messif.algorithms.Algorithm.AlgorithmConstructor
 
Nested classes/interfaces inherited from interface messif.buckets.split.SplittableAlgorithm
messif.buckets.split.SplittableAlgorithm.SplittableAlgorithmResult
 
Field Summary
protected  messif.buckets.BucketDispatcher bucketDispatcher
          dispatcher of all leaf buckets
protected  java.util.Map<java.lang.Object,SearchQueue<java.io.Serializable>> incManager
          map keeps IDs of operations for the incremental nearest neighbor search algorithm
protected  float insRadius
          radius for multiway insertion of a new object
protected  long intNodeCap
          maximum internal node capacity
protected  long intNodeCapInBucketAlgorithm
          maximum internal node capacity of the tree stored in every bucket (when using of an algorithm in the buckets)
protected  boolean isAlgorithmInBucket
          indicates the using of M-tree algorithm in the buckets
protected  long leafCap
          maximum leaf capacity
protected  long leafCapInBucketAlgorithm
          maximum leaf capacity of the tree stored in every bucket (when using of an algorithm in the buckets)
protected  int maxSpanningTree
          maximum number of objects which are selected by splitNode_SlimDown method to build a minimum spanning tree
protected  boolean multiwayInsertion
          indicates whether a new object is inserted by multiway algorithm
protected  int nhr
           
protected  int npd
           
protected  messif.objects.LocalAbstractObject[] pivots
          fixed array of pivots
protected  Node root
          root of the tree
 
Fields inherited from class messif.algorithms.Algorithm
log, maximalConcurrentOperations
 
Constructor Summary
MTree(long intNodeCap, long leafCap)
          Creates M-tree algorithm.
MTree(long intNodeCap, long leafCap, float insRadius, int maxSpanningTree, boolean isAlgorithmInBucket, long intNodeCapInBucketAlgorithm, long leafCapInBucketAlgorithm)
          Creates M-tree algorithm.
MTree(long intNodeCap, long leafCap, int pivotCount, messif.objects.util.AbstractObjectIterator<messif.objects.LocalAbstractObject> pivotIterator, int npd, int nhr)
          Creates M-tree algorithm.
MTree(long intNodeCap, long leafCap, int pivotCount, messif.objects.util.AbstractObjectIterator<messif.objects.LocalAbstractObject> pivotIterator, int npd, int nhr, float insRadius, int maxSpanningTree, boolean isAlgorithmInBucket, long intNodeCapInBucketAlgorithm, long leafCapInBucketAlgorithm)
          Creates M-tree algorithm.
MTree(long intNodeCap, long leafCap, int pivotCount, messif.objects.util.AbstractObjectIterator<messif.objects.LocalAbstractObject> pivotIterator, int npd, int nhr, float insRadius, int maxSpanningTree, boolean isAlgorithmInBucket, long intNodeCapInBucketAlgorithm, long leafCapInBucketAlgorithm, java.lang.Class<? extends messif.buckets.LocalBucket> bucketClass, java.util.Map<java.lang.String,java.lang.Object> bucketClassParams)
           
MTree(long intNodeCap, long leafCap, messif.objects.LocalAbstractObject[] pivots, int npd, int nhr, float insRadius, int maxSpanningTree, boolean isAlgorithmInBucket, long intNodeCapInBucketAlgorithm, long leafCapInBucketAlgorithm)
           
MTree(long intNodeCap, long leafCap, messif.objects.LocalAbstractObject[] pivots, int npd, int nhr, float insRadius, int maxSpanningTree, boolean isAlgorithmInBucket, long intNodeCapInBucketAlgorithm, long leafCapInBucketAlgorithm, java.lang.Class<? extends messif.buckets.LocalBucket> bucketClass, java.util.Map<java.lang.String,java.lang.Object> bucketClassParams)
          Creates M-tree algorithm.
 
Method Summary
 messif.buckets.BucketErrorCode addObject(messif.objects.LocalAbstractObject object)
          Inserts a new object into the tree.
 boolean approxKNN(messif.operations.query.ApproxKNNQueryOperation kNNOper)
          Approximates the evaluation of k nearest neighbors query.
 MTree clone()
          Clones the tree (along with all stored objects) exloiting the process of serialization.
 MTree cloneWithoutObjects()
          Creates new empty M-tree with same a structure (parameters) as current this, but without stored objects.
 void clonningSplit(messif.buckets.split.SplitPolicy sp, boolean include)
          Removes all irrelevant objects from this tree according to the given splitNode_SlimDown policy.
 boolean deleteObject(messif.operations.data.DeleteOperation delOper)
          Deletes the specific object from the tree.
 void deletingSplit(messif.buckets.split.SplitPolicy sp, messif.buckets.split.SplittableAlgorithm.SplittableAlgorithmResult result)
          Splits this tree into two trees according to the given splitNode_SlimDown policy.
 void finalize()
           
 java.util.Collection<messif.buckets.LocalBucket> getAllBuckets()
          Returns a list of all buckets of the tree.
 java.util.List<LeafNode> getAllLeaves()
          Returns a list of all leaves of the tree.
 messif.objects.util.AbstractObjectIterator<messif.objects.LocalAbstractObject> getAllObjects()
          Looks for all objects stored in the tree.
 void getAllObjectsQueryOperation(messif.operations.query.GetAllObjectsQueryOperation qo)
          Looks for all objects stored in the tree.
 messif.buckets.BucketDispatcher getBucketDispatcher()
          Returns the bucket dispatcher of the tree.
 void getObjectByLocatorOperation(messif.operations.query.GetObjectByLocatorOperation qo)
          Random-access query for SAPIR API.
 java.lang.Class<? extends messif.objects.LocalAbstractObject> getObjectClass()
          Returns the class of objects indexed by this algorithm.
 int getObjectCount()
          Returns the number of objects stored in the tree.
 void getObjectsByLocatorsOperation(messif.operations.query.GetObjectsByLocatorsOperation qo)
          Random-access query for SAPIR API.
 messif.objects.LocalAbstractObject[] getPivots()
          Returns the copy of fixed array of pivots.
 Node getRoot()
          Returns the root of the tree.
 boolean incrementalNN(messif.operations.query.IncrementalNNQueryOperation incOper)
          Incremental nearest neighbor search.
 boolean insert(messif.operations.data.InsertOperation insOper)
          Inserts a new object into the tree.
 boolean kNN(messif.operations.query.KNNQueryOperation kNNOper)
          k-NN search operation Performs the k-nearest neighbor search operation with given KNNQueryOperation object.
static MTree loadFromFile(java.lang.String fileName)
          Loads the M-tree from a file specified by filename.
protected  void print(Node n)
          Recursive method for printTree.
 void printStatistics()
          Prints the statistics of the tree (the number of internal nodes, the number of leaves, the number of all objects and the number of slim nodes - nodes with only one stored object).
 void printTree()
          Prints a structure of the whole tree (all nodes with their objects).
protected  void processNode(InternalNode node, SearchQueue queue, java.util.Map<messif.objects.LocalAbstractObject,java.lang.Float> pd, messif.objects.LocalAbstractObject queryObject, float radius)
          Process an internal node from M-Tree queue.
protected  void processNode(LeafNode node, java.util.Map<messif.objects.LocalAbstractObject,java.lang.Float> pd, messif.operations.query.KNNQueryOperation kNNOper)
          Process a leaf node from M-Tree queue.
protected  void processNode(LeafNode node, SearchQueue<java.io.Serializable> queue, messif.objects.LocalAbstractObject queryObject)
          Process a leaf node from M-Tree queue.
 void saveToFile(java.lang.String fileName)
          Saves the tree into a file specified by filename.
 void setMultiwayInsertion(boolean multiwayInsertion)
          Sets the type of inserting algorithm (singleway or multiway insertion).
 void split(messif.buckets.split.SplitPolicy sp, messif.buckets.split.SplittableAlgorithm.SplittableAlgorithmResult result, int whoStays)
          Splits this tree into two trees according to the given splitNode_SlimDown policy.
 java.lang.String toString()
          Overrided class Object
 
Methods inherited from class messif.algorithms.Algorithm
backgroundExecute, backgroundExecuteOperation, backgroundExecuteOperation, destroy, execute, executeOperation, getAnnotatedConstructors, getAnnotatedConstructorsArray, getConstructorArgumentDescriptions, getConstructorDescription, getConstructorDescriptionSimple, getExecutorParamClasses, getFirstSupportedOperation, getName, getOperationStatistics, getQueryAnswer, getQueryAnswer, getRunningOperationsCount, getSupportedOperations, getSupportedOperations, resetOperationStatistics, restoreFromFile, restoreFromFile, statisticsAfterOperation, statisticsBeforeOperation, storeToFile, waitBackgroundExecuteOperation, waitBackgroundExecuteOperation
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

intNodeCap

protected final long intNodeCap
maximum internal node capacity


leafCap

protected final long leafCap
maximum leaf capacity


pivots

protected final messif.objects.LocalAbstractObject[] pivots
fixed array of pivots


npd

protected final int npd

nhr

protected final int nhr

root

protected Node root
root of the tree


bucketDispatcher

protected messif.buckets.BucketDispatcher bucketDispatcher
dispatcher of all leaf buckets


multiwayInsertion

protected boolean multiwayInsertion
indicates whether a new object is inserted by multiway algorithm


insRadius

protected float insRadius
radius for multiway insertion of a new object


maxSpanningTree

protected int maxSpanningTree
maximum number of objects which are selected by splitNode_SlimDown method to build a minimum spanning tree


isAlgorithmInBucket

protected final boolean isAlgorithmInBucket
indicates the using of M-tree algorithm in the buckets


intNodeCapInBucketAlgorithm

protected final long intNodeCapInBucketAlgorithm
maximum internal node capacity of the tree stored in every bucket (when using of an algorithm in the buckets)


leafCapInBucketAlgorithm

protected final long leafCapInBucketAlgorithm
maximum leaf capacity of the tree stored in every bucket (when using of an algorithm in the buckets)


incManager

protected java.util.Map<java.lang.Object,SearchQueue<java.io.Serializable>> incManager
map keeps IDs of operations for the incremental nearest neighbor search algorithm

Constructor Detail

MTree

public MTree(long intNodeCap,
             long leafCap)
      throws messif.algorithms.AlgorithmMethodException,
             java.lang.InstantiationException
Creates M-tree algorithm.

Parameters:
intNodeCap - internal node capacity
leafCap - leaf capacity
Throws:
messif.algorithms.AlgorithmMethodException
java.lang.InstantiationException

MTree

public MTree(long intNodeCap,
             long leafCap,
             float insRadius,
             int maxSpanningTree,
             boolean isAlgorithmInBucket,
             long intNodeCapInBucketAlgorithm,
             long leafCapInBucketAlgorithm)
      throws messif.algorithms.AlgorithmMethodException,
             java.lang.InstantiationException
Creates M-tree algorithm.

Parameters:
intNodeCap - internal node capacity
leafCap - leaf capacity
insRadius - multi-way insertion radius
maxSpanningTree - maximum number of objects creating spanning tree
isAlgorithmInBucket - using of M-tree algorithm in the buckets
intNodeCapInBucketAlgorithm - maximum internal node capacity of the tree stored in every bucket
leafCapInBucketAlgorithm - maximum leaf capacity of the tree stored in every bucket
Throws:
messif.algorithms.AlgorithmMethodException
java.lang.InstantiationException

MTree

public MTree(long intNodeCap,
             long leafCap,
             int pivotCount,
             messif.objects.util.AbstractObjectIterator<messif.objects.LocalAbstractObject> pivotIterator,
             int npd,
             int nhr)
      throws messif.algorithms.AlgorithmMethodException,
             java.lang.InstantiationException
Creates M-tree algorithm.

Parameters:
intNodeCap - internal node capacity
leafCap - leaf capacity
pivotCount - number of pivots to read
pivotIterator - object iterator for pivots
npd - number of pivots used in leaves
nhr - number of pivots used in internal nodes
Throws:
messif.algorithms.AlgorithmMethodException
java.lang.InstantiationException

MTree

public MTree(long intNodeCap,
             long leafCap,
             int pivotCount,
             messif.objects.util.AbstractObjectIterator<messif.objects.LocalAbstractObject> pivotIterator,
             int npd,
             int nhr,
             float insRadius,
             int maxSpanningTree,
             boolean isAlgorithmInBucket,
             long intNodeCapInBucketAlgorithm,
             long leafCapInBucketAlgorithm)
      throws java.lang.InstantiationException,
             messif.algorithms.AlgorithmMethodException
Creates M-tree algorithm.

Parameters:
intNodeCap - internal node capacity
leafCap - leaf capacity
pivotCount - number of pivots to read
pivotIterator - object iterator for pivots
npd - number of pivots used in leaves
nhr - number of pivots used in internal nodes
insRadius - multi-way insertion radius
maxSpanningTree - maximum number of objects creating spanning tree
isAlgorithmInBucket - using of M-tree algorithm in the buckets
intNodeCapInBucketAlgorithm - maximum internal node capacity of the tree stored in every bucket
leafCapInBucketAlgorithm - maximum leaf capacity of the tree stored in every bucket
Throws:
java.lang.InstantiationException
messif.algorithms.AlgorithmMethodException

MTree

public MTree(long intNodeCap,
             long leafCap,
             messif.objects.LocalAbstractObject[] pivots,
             int npd,
             int nhr,
             float insRadius,
             int maxSpanningTree,
             boolean isAlgorithmInBucket,
             long intNodeCapInBucketAlgorithm,
             long leafCapInBucketAlgorithm)
      throws messif.algorithms.AlgorithmMethodException,
             java.lang.InstantiationException
Throws:
messif.algorithms.AlgorithmMethodException
java.lang.InstantiationException

MTree

public MTree(long intNodeCap,
             long leafCap,
             int pivotCount,
             messif.objects.util.AbstractObjectIterator<messif.objects.LocalAbstractObject> pivotIterator,
             int npd,
             int nhr,
             float insRadius,
             int maxSpanningTree,
             boolean isAlgorithmInBucket,
             long intNodeCapInBucketAlgorithm,
             long leafCapInBucketAlgorithm,
             java.lang.Class<? extends messif.buckets.LocalBucket> bucketClass,
             java.util.Map<java.lang.String,java.lang.Object> bucketClassParams)
      throws java.lang.InstantiationException,
             messif.algorithms.AlgorithmMethodException
Throws:
java.lang.InstantiationException
messif.algorithms.AlgorithmMethodException

MTree

public MTree(long intNodeCap,
             long leafCap,
             messif.objects.LocalAbstractObject[] pivots,
             int npd,
             int nhr,
             float insRadius,
             int maxSpanningTree,
             boolean isAlgorithmInBucket,
             long intNodeCapInBucketAlgorithm,
             long leafCapInBucketAlgorithm,
             java.lang.Class<? extends messif.buckets.LocalBucket> bucketClass,
             java.util.Map<java.lang.String,java.lang.Object> bucketClassParams)
      throws messif.algorithms.AlgorithmMethodException,
             java.lang.InstantiationException
Creates M-tree algorithm.

Parameters:
intNodeCap - internal node capacity
leafCap - leaf capacity
pivots - array of pivots
npd - number of pivots used in leaves
nhr - number of pivots used in internal nodes
insRadius - multi-way insertion radius
maxSpanningTree - maximum number of objects creating spanning tree
isAlgorithmInBucket - using of M-tree algorithm in the buckets
intNodeCapInBucketAlgorithm - maximum internal node capacity of the tree stored in every bucket
leafCapInBucketAlgorithm - maximum leaf capacity of the tree stored in every bucket
Throws:
messif.algorithms.AlgorithmMethodException
java.lang.InstantiationException
Method Detail

getRoot

public Node getRoot()
Returns the root of the tree.

Returns:
the root of the tree

getPivots

public messif.objects.LocalAbstractObject[] getPivots()
Returns the copy of fixed array of pivots.

Returns:
the copy of fixed array of pivots

getBucketDispatcher

public messif.buckets.BucketDispatcher getBucketDispatcher()
Returns the bucket dispatcher of the tree.

Returns:
the bucket dispatcher of the tree

setMultiwayInsertion

public void setMultiwayInsertion(boolean multiwayInsertion)
Sets the type of inserting algorithm (singleway or multiway insertion).

Parameters:
multiwayInsertion - indicates whether new objects will be inserted by multiway algorithm

getAllLeaves

public java.util.List<LeafNode> getAllLeaves()
Returns a list of all leaves of the tree.

Returns:
a list of all leaves of the tree

getAllBuckets

public java.util.Collection<messif.buckets.LocalBucket> getAllBuckets()
Returns a list of all buckets of the tree.

Returns:
a list of all buckets of the tree

cloneWithoutObjects

public MTree cloneWithoutObjects()
Creates new empty M-tree with same a structure (parameters) as current this, but without stored objects.

Returns:
new empty M-tree with same a structure (parameters) as current this, but without stored objects

getObjectClass

public java.lang.Class<? extends messif.objects.LocalAbstractObject> getObjectClass()
Returns the class of objects indexed by this algorithm. This methods returns the class of the first object stored in the first bucket.

Overrides:
getObjectClass in class messif.algorithms.Algorithm
Returns:
the class of objects indexed by this algorithm

clonningSplit

public void clonningSplit(messif.buckets.split.SplitPolicy sp,
                          boolean include)
                   throws messif.buckets.BucketStorageException
Removes all irrelevant objects from this tree according to the given splitNode_SlimDown policy.

Throws:
messif.buckets.BucketStorageException

deletingSplit

public void deletingSplit(messif.buckets.split.SplitPolicy sp,
                          messif.buckets.split.SplittableAlgorithm.SplittableAlgorithmResult result)
                   throws messif.buckets.BucketStorageException,
                          java.lang.InstantiationException
Splits this tree into two trees according to the given splitNode_SlimDown policy.

Throws:
messif.buckets.BucketStorageException
java.lang.InstantiationException

getAllObjectsQueryOperation

public void getAllObjectsQueryOperation(messif.operations.query.GetAllObjectsQueryOperation qo)
Looks for all objects stored in the tree.


getObjectsByLocatorsOperation

public void getObjectsByLocatorsOperation(messif.operations.query.GetObjectsByLocatorsOperation qo)
Random-access query for SAPIR API. Implemented as (index) searching all buckets.


getObjectByLocatorOperation

public void getObjectByLocatorOperation(messif.operations.query.GetObjectByLocatorOperation qo)
Random-access query for SAPIR API. Implemented as (index) searching all buckets.


deleteObject

public boolean deleteObject(messif.operations.data.DeleteOperation delOper)
Deletes the specific object from the tree.

Returns:
false if the tree does not contain the specific object

kNN

public boolean kNN(messif.operations.query.KNNQueryOperation kNNOper)
k-NN search operation Performs the k-nearest neighbor search operation with given KNNQueryOperation object. The answer is held in the KNNQueryOperation object.

Parameters:
kNNOper - kNN query operation which carries the query object and k as well as the response list.
Returns:
returns true

processNode

protected void processNode(LeafNode node,
                           java.util.Map<messif.objects.LocalAbstractObject,java.lang.Float> pd,
                           messif.operations.query.KNNQueryOperation kNNOper)
Process a leaf node from M-Tree queue. Leaf's associated bucket is processed by the specified query operation.

Parameters:
node - the leaf node to be processed
pd - precomputed distances to specific objects
kNNOper - the kNN operation processed on the leaf

processNode

protected void processNode(LeafNode node,
                           SearchQueue<java.io.Serializable> queue,
                           messif.objects.LocalAbstractObject queryObject)
Process a leaf node from M-Tree queue. Leaf's associated objects (from bucket) are added to queue.

Parameters:
node - the leaf node to be processed
queue - the queue to add the objects to
queryObject - the query object used for computing distances

processNode

protected void processNode(InternalNode node,
                           SearchQueue queue,
                           java.util.Map<messif.objects.LocalAbstractObject,java.lang.Float> pd,
                           messif.objects.LocalAbstractObject queryObject,
                           float radius)
Process an internal node from M-Tree queue. The queue is updated with node's internal entries that can't be filtered out.

Parameters:
node - the internal node to be processed
queue - the queue into which to add nodes
pd - precomputed distances to specific objects
queryObject - the query object used for filtering
radius - the radius used for filtering

incrementalNN

public boolean incrementalNN(messif.operations.query.IncrementalNNQueryOperation incOper)
Incremental nearest neighbor search. Incrementally returns the nearest objects to the given object. The objects are returned in the operation's response list. This implementation respects the minimum number of nearest neighbors specified in the operation.

Parameters:
incOper - Incremental nearest neighbor query operation which carries the query object
Returns:
returns true

approxKNN

public boolean approxKNN(messif.operations.query.ApproxKNNQueryOperation kNNOper)
Approximates the evaluation of k nearest neighbors query. Looks for the k-nearest objects to the given object. Note that the searching is approximate therefor all the nearest objects needn't be returned. The neighbors (objects) are returned in the response in the operation.

Parameters:
kNNOper - the operation which specifies the query object and the number of neighbors to retrieve
Returns:
returns true

insert

public boolean insert(messif.operations.data.InsertOperation insOper)
Inserts a new object into the tree. A leaf into which the new object is inserted is chosen by inserting singleway or multiway algorithm (it depends on multiwayInsertion variable).

Returns:
false if the size of inserting object is greater than the capacity of an internal node or a leaf

split

public void split(messif.buckets.split.SplitPolicy sp,
                  messif.buckets.split.SplittableAlgorithm.SplittableAlgorithmResult result,
                  int whoStays)
           throws messif.buckets.BucketStorageException
Splits this tree into two trees according to the given splitNode_SlimDown policy.

Specified by:
split in interface messif.buckets.split.SplittableAlgorithm
Parameters:
whoStays - identification of a partition whose objects stay in this bucket.
Throws:
messif.buckets.BucketStorageException

addObject

public messif.buckets.BucketErrorCode addObject(messif.objects.LocalAbstractObject object)
Inserts a new object into the tree. A leaf into which the new object is inserted is chosen by inserting singleway or multiway algorithm (it depends on multiwayInsertion variable).

Returns:
bucket error code after inserting the object

getObjectCount

public int getObjectCount()
Returns the number of objects stored in the tree.

Returns:
the number of objects stored in the tree

getAllObjects

public messif.objects.util.AbstractObjectIterator<messif.objects.LocalAbstractObject> getAllObjects()
Looks for all objects stored in the tree.

Returns:
object iterator of all objects stored in the tree

clone

public MTree clone()
Clones the tree (along with all stored objects) exloiting the process of serialization.

Overrides:
clone in class java.lang.Object

saveToFile

public void saveToFile(java.lang.String fileName)
Saves the tree into a file specified by filename.

Parameters:
fileName - the file name into which the tree is saved

loadFromFile

public static MTree loadFromFile(java.lang.String fileName)
Loads the M-tree from a file specified by filename.

Parameters:
fileName - the file name from which the tree is loaded
Returns:
the loaded M-tree from file specified by filename

printStatistics

public void printStatistics()
Prints the statistics of the tree (the number of internal nodes, the number of leaves, the number of all objects and the number of slim nodes - nodes with only one stored object).


printTree

public void printTree()
Prints a structure of the whole tree (all nodes with their objects).


print

protected void print(Node n)
Recursive method for printTree.


toString

public java.lang.String toString()
Overrided class Object

Overrides:
toString in class java.lang.Object

finalize

public void finalize()
              throws java.lang.Throwable
Overrides:
finalize in class messif.algorithms.Algorithm
Throws:
java.lang.Throwable