m-tree

File:M-tree_built_with_MMRad_split.png. Every blue sphere (leaf) is contained in a red sphere (directory nodes). Leaves overlap, but not too much; directory nodes overlap much more here.]]

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 $n$ and leaf $l$ residing in a particular node $N$ is at most distance $r$ from $N$, and every node $n$ and leaf $l$ with node parent $N$ keep the distance from it.

An M-tree has these components and sub-components:

1. Non-leaf nodes
2. A set of routing objects N_RO.
3. Pointer to Node's parent object O_p.
4. Leaf nodes
5. A set of objects N_O.
6. Pointer to Node's parent object O_p.
7. Routing Object
8. (Feature value of) routing object O_r.
9. Covering radius r(O_r).
10. Pointer to covering tree T(O_r).
11. Distance of O_r from its parent object d(O_r,P(O_r))
12. Object
13. (Feature value of the) object O_j.
14. Object identifier oid(O_j).
15. Distance of O_j from its parent object d(O_j,P(O_j))

The main idea is first to find a leaf node {{mvar|N}} where the new object {{mvar|O}} belongs. If {{mvar|N}} is not full then just attach it to {{mvar|N}}. If {{mvar|N}} is full then invoke a method to split {{mvar|N}}. The algorithm is as follows:

{{algorithm-begin|name=Insert}}

Input: Node {{mvar|N}} of M-Tree {{mvar|MT}}, {{nowrap|Entry $O\_\{n\}$}}

Output: A new instance of {{mvar|MT}} containing all entries in original {{nowrap|{{mvar|MT}} plus $O\_\{n\}$}}

{{nowrap|$N\_\{e\}\; \backslash gets\; N$}}'s routing objects or objects

if {{mvar|N}} is not a leaf then

{

/* Look for entries that the new object fits into */

{{nowrap|let $N\_\{in\}$ be routing objects from $N\_\{e\}$'s set of routing objects $N\_\{RO\}$}} {{nowrap|such that $d(O\_\{r\},\; O\_\{n\})\; \backslash le\; r(O\_\{r\})$}}

{{nowrap|if $N\_\{in\}$ is not empty then}}

{

/* If there are one or more entry, then look for an entry such that is closer to the new object */

{{nowrap|$O\_\{r\}^\{*\}\; \backslash gets\; \backslash min\_\{O\_\{r\}\backslash in\; N\_\{in\}\}\; d(O\_\{r\},\; O\_\{n\})$}}

}

else

{

/* If there are no such entry, then look for an object with minimal distance from */

/* its covering radius's edge to the new object */

{{nowrap|$O\_\{r\}^\{*\}\; \backslash gets\; \backslash min\_\{O\_\{r\}\backslash in\; N\_\{in\}\}\; d(O\_\{r\},\; O\_\{n\})\; -\; r(O\_\{r\})$}}

/* Upgrade the new radii of the entry */

{{nowrap|$r(O\_\{r\}^\{*\})\; \backslash gets\; d(O\_\{r\}^\{*\},\; O\_\{n\})$}}

}

/* Continue inserting in the next level */

{{nowrap|return insert($T(O\_\{r\}^\{*\}),\; O\_\{n\}$);}}

else

{

/* If the node has capacity then just insert the new object */

if {{mvar|N}} is not full then

{ {{nowrap|store($N,\; O\_\{n\}$)}} }

/* The node is at full capacity, then it is needed to do a new split in this level */

else

{ {{nowrap|split($N,\; O\_\{n\}$)}} }

}

{{algorithm-end}}

If the split method arrives to the root of the tree, then it choose two routing objects from {{mvar|N}}, and creates two new nodes containing all the objects in original {{mvar|N}}, and store them into the new root. If split methods arrives to a node {{mvar|N}} that is not the root of the tree, the method choose two new routing objects from {{mvar|N}}, re-arrange every routing object in {{mvar|N}} in two new nodes $N\_\{1\}$ and $N\_\{2\}$, and store these new nodes in the parent node $N\_\{p\}$ of original {{mvar|N}}. The split must be repeated if $N\_\{p\}$ has not enough capacity to store $N\_\{2\}$. The algorithm is as follow:

{{algorithm-begin|name=Split}}

Input: Node {{mvar|N}} of M-Tree {{mvar|MT}}, {{nowrap|Entry $O\_\{n\}$}}

Output: A new instance of {{mvar|MT}} containing a new partition.

/* The new routing objects are now all those in the node plus the new routing object */

let be {{mvar|NN}} entries of {{nowrap|$N\; \backslash cup\; O$}}

if {{mvar|N}} is not the root then

{

/*Get the parent node and the parent routing object*/

{{nowrap|let $O\_\{p\}$ be the parent routing object of {{mvar|N}}}}

{{nowrap|let $N\_\{p\}$ be the parent node of {{mvar|N}}}}

}

/* This node will contain part of the objects of the node to be split */

Create a new node {{mvar|N'}}

/* Promote two routing objects from the node to be split, to be new routing objects */

Create new objects {{nowrap|$O\_\{p1\}$ and $O\_\{p2\}$.}}

Promote({{nowrap|$N,\; O\_\{p1\},\; O\_\{p2\}$}})

/* Choose which objects from the node being split will act as new routing objects */

Partition({{nowrap|$N,\; O\_\{p1\},\; O\_\{p2\},\; N\_\{1\},\; N\_\{2\}$}})

/* Store entries in each new routing object */

{{nowrap|Store $N\_\{1\}$'s entries in {{mvar|N}} and $N\_\{2\}$'s entries in {{mvar|N'}}}}

if {{mvar|N}} is the current root then

{

/* Create a new node and set it as new root and store the new routing objects */

{{nowrap|Create a new root node $N\_\{p\}$}}

{{nowrap|Store $O\_\{p1\}$ and $O\_\{p2\}$ in $N\_\{p\}$}}

}

else

{

/* Now use the parent routing object to store one of the new objects */

{{nowrap|Replace entry $O\_\{p\}$ with entry $O\_\{p1\}$ in $N\_\{p\}$}}

{{nowrap|if $N\_\{p\}$ is no full then}}

{

/* The second routing object is stored in the parent only if it has free capacity */

{{nowrap|Store $O\_\{p2\}$ in $N\_\{p\}$}}

}

else

{

/*If there is no free capacity then split the level up*/

{{nowrap|split($N\_\{p\},\; O\_\{p2\}$)}}

}

}

{{algorithm-end}}

A range query is where a minimum similarity/maximum distance value is specified.

For a given query object {{tmath|Q \in D}} and a maximum search distance

{{tmath|r(Q)}}, the range query range(Q, r(Q)) selects all the indexed objects {{tmath|O_j}} such that {{tmath|d(O_j, Q) \le r(Q)}}.{{cite web|title=Indexing Metric Spaces with M-tree|url=http://www-db.deis.unibo.it/research/papers/SEBD97.pdf|work=Department of Computer Science and Engineering|publisher=University of Bologna|access-date=19 November 2013|author1=P. Ciaccia |author2=M. Patella |author3=F. Rabitti |author4=P. Zezula |page=3}}

Algorithm RangeSearch starts from the root node and recursively traverses all the paths which cannot be excluded from leading to qualifying objects.

{{algorithm-begin|name=RangeSearch}}

Input: Node {{mvar|N}} of M-Tree MT, {{mvar|Q}}: query object, {{nowrap|$r(Q)$}}: search radius

Output: all the DB objects {{nowrap|such that $d(Oj,\; Q)\; \backslash le\; r(Q)$}}

{

{{nowrap|let $O\_\{p\}$ be the parent object of node {{mvar|N}};}}

if {{mvar|N}} is not a leaf then {

{{nowrap|for each entry($O\_\{r\}$) in {{mvar|N}}}} do {

{{nowrap|if $|\; d(O\_\{p\},\; Q)\; -\; d(O\_\{r\},\; O\_\{p\})\; |\; \backslash le\; r(Q)\; +\; r(O\_\{r\})$}} then {

{{nowrap|Compute $d(O\_\{r\},\; Q)$;}}

{{nowrap|if $d(O\_\{r\},\; Q)\; \backslash le\; r(Q)\; +r(O\_\{r\})$}} then

{{nowrap|RangeSearch(*ptr($T(O\_\{r\}$)),{{mvar|Q}},$r(Q)$);}}

}

}

}

else {

{{nowrap|for each entry($O\_\{j\}$) in {{mvar|N}}}} do {

{{nowrap|if $|\; d(O\_\{p\},\; Q)\; -\; d(O\_\{j\},\; O\_\{p\})\; |\; \backslash le\; r(Q)$}} then {

{{nowrap|Compute $d(O\_\{j\},\; Q)$;}}

{{nowrap|if $d(O\_\{j\},\; Q)$ ≤ $r(Q)$}} then

{{nowrap|add $oid(O\_\{j\})$ to the result;}}

}

}

}

}

{{algorithm-end}}

• $oid(O\_\{j\})$ is the identifier of the object which resides on a separate data file.
• $T(O\_\{r\})$ is a sub-tree – the covering tree of $O\_\{r\}$

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.

• Segment tree
• Interval tree - A degenerate R-tree for one dimension (usually time)
• Bounding volume hierarchy
• Spatial index
• GiST
• Cover tree

{{reflist}}

{{CS-Trees}}

{{Portal bar|Technology|Mathematics|Internet|Science}}

{{DEFAULTSORT:M-Tree}}

Category:Trees (data structures)

Category:Database index techniques

Category:Geometric data structures