Overview
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 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 and leaf with node parent keep the distance from it.M-Tree construction
Components
An M-Tree has these components and sub-components: # Non-leaf nodes ## A set of routing objects N''RO''. ## Pointer to Node's parent object O''p''. # Leaf nodes ## A set of objects N''O''. ## Pointer to Node's parent object O''p''. # Routing Object ## (Feature value of) routing object O''r''. ## Covering radius r(O''r''). ## Pointer to covering tree T(O''r''). ## Distance of O''r'' from its parent object d(O''r'',P(O''r'')) # Object ## (Feature value of the) object O''j''. ## Object identifier oid(O''j''). ## Distance of O''j'' from its parent object d(O''j'',P(O''j''))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: Input: Node of M-Tree , Output: A new instance of containing all entries in original 's routing objects or objects if is not a leaf then } else } /* Upgrade the new radii of the entry */ } /* Continue inserting in the next level */ elseSplit
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 these 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: Input: Node of M-Tree , 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 /* 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 */ Create new objects Promote() /* Choose which objects from the node being split will act as new routing objects */ Partition() /* Store entries in each new routing object */ if is the current root then elseM-Tree Queries
Range Query
A range query is where a minimum similarity/maximum distance value is specified. For a given query object and a maximum search distance , the range query range(Q, r(Q)) selects all the indexed objects such that . Algorithm RangeSearch starts from the root node and recursively traverses all the paths which cannot be excluded from leading to qualifying objects. Input: Node of M-Tree MT, : query object, : search radius Output: all the DB objects * is the identifier of the object which resides on a separate data file. * is a sub-tree – the covering tree ofk-NN queries
K Nearest Neighbor (k-NN) query takes the cardinality of the input set as an input parameter. For a given query object Q ∈ D and an integer k ≥ 1, the k-NN query NN(Q, k) selects the k indexed objects which have the shortest distance from Q, according to the distance function d.See also
* Segment tree * Interval tree - A degenerate R-Tree for 1 dimension (usually time). *References
{{DEFAULTSORT:M-Tree Trees (data structures) Database index techniques Geometric data structures