M-trees are tree data structures that are similar to R-trees and B-trees. It is constructed using a metric and relies on the triangle inequality for efficient range and k-NN queries. While M-trees can perform well in many conditions, the tree can also have large overlap and there is no clear strategy on how to best avoid overlap. In addition, it can only be used for distance functions that satisfy the triangle inequality, while many advanced dissimilarity functions used in information retrieval do not satisfy this.[1]
Overview
2D M-Tree visualized using
ELKI. The tree has a single level of leaf nodes. Due to a suboptimal split heuristic, there is a large overlap.
As in any Tree-based data structure, the M-Tree is composed of Nodes and Leaves. In each node there is a data object that identifies it uniquely and a pointer to a sub-tree where its children reside. Every leaf has several data objects. For each node there is a radius r that defines a Ball in the desired metric space. Thus, every node and leaf residing in a particular node is at most distance from , and every node n and leaf l with node parent N keep the distance from it.
M-Tree construction
Components
An M-Tree has these components and sub-components:
- Root.
- Routing object O.
- Radius Or.
- A set of Nodes or (exclusive) Leafs.
- Node.
- Routing object O.
- Radius Or.
- Distance from this node to its parent Op.
- A set of Nodes or (exclusive) Leafs.
- Leaf.
- Routing object O.
- Radius Or.
- Distance from this leaf to its parent Op.
- Objects.
- Objects.
- Feature value (usually a d-dimensional vector).
Insert
The main idea is first to find a leaf node where the new object belongs. If is not full then just attach it to . If is full then invoke a method to split . The algorithm is as follows:
Algorithm Insert Input: Node of M-Tree , Entry Output: A new instance of containing all entries in original plus
← Entries of node if is not a leaf then { /*Look for entries that the new object fits into*/ let be entries such that if is not empty then { /*If there are one or more entry, then look for an entry such that is closer to the new object*/ let be such that is minimum } else { /*If there are no such entry, then look for an entry with minimal distance from its edge to the new object*/ let be such that is minimum /*Upgrade the new radii of the entry*/ = } /*Continue inserting in the next level*/ return insert(, ); else { /*If the node has capacity then just insert the new object*/ if is not full then { store(, ) } /*The node is at full capacity, then it is needed to do a new split in this level*/ else { split(, ) } }
- "←" is a shorthand for "changes to". For instance, "largest ← item" means that the value of largest changes to the value of item.
- "return" terminates the algorithm and outputs the value that follows.
Split
If the split method arrives to the root of the tree, then it choose two routing objects from , and creates two new nodes containing all the objects in original , and store them into the new root. If split methods arrives to a node that is not the root of the tree, the method choose two new routing objects from , re-arrange every routing object in in two new nodes and , and store this new nodes in the parent node of original . The split must be repeated if has not enough capacity to store . The algorithm is as follow:
Algorithm Split Input: Node of M-Tree , Entry Output: A new instance of containing a new partition.
/*The new routing objects are now all those in the node plus the new routing object*/ let be entries of if is not the root then { /*Get the parent node and the parent routing object*/ let be the parent routing object of let be the parent node of } /*This node will contain part of the objects of the node to be split*/ Create a new node /*Promote two routing objects from the node to be split, to be new routing objects*/ Promote(, , ) /*Choose which objects from the node being split will act as new routing objects*/ Partition(, , , , ) /*Store entries in each new routing object*/ Store 's entries in and 's entries in if is the current root then { /*Create a new node and set it as new root and store the new routing objects*/ Create a new root node Store and in } else { /*Now use the parent rouing object to store one of the new objects*/ Replace entry with entry in if is no full then { /*The second routinb object is stored in the parent only if it has free capacity*/ Store in } else { /*If there is no free capacity then split the level up*/ split(, ) } }
- "←" is a shorthand for "changes to". For instance, "largest ← item" means that the value of largest changes to the value of item.
- "return" terminates the algorithm and outputs the value that follows.
M-Tree Queries
Range queries
Range queries
k-NN queries
See also
References