Movatterモバイル変換

[0]ホーム

Jump to content

M-tree

Italiano

Edit links

From Wikipedia, the free encyclopedia

Tree data structure

This articlemay be too technical for most readers to understand. Pleasehelp improve it tomake it understandable to non-experts, without removing the technical details.(October 2021) (Learn how and when to remove this message)

Incomputer science,M-trees aretree data structures that are similar toR-trees andB-trees. It is constructed using ametric and relies on thetriangle inequality for efficient range andk-nearest neighbor (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 fordistance functions that satisfy the triangle inequality, while many advanced dissimilarity functions used ininformation retrieval do not satisfy this.^[1]

Overview

[edit]

2D M-Tree visualized usingELKI. 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 {\displaystyle r}$ that defines a Ball in the desired metric space. Thus, every node $n {\displaystyle n}$ and leaf $l {\displaystyle l}$ residing in a particular node $N {\displaystyle N}$ is at most distance $r {\displaystyle r}$ from $N {\displaystyle N}$ , and every node $n {\displaystyle n}$ and leaf $l {\displaystyle l}$ with node parent $N {\displaystyle N}$ keep the distance from it.

M-tree construction

[edit]

Components

[edit]

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

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

Insert

[edit]

The main idea is first to find a leaf nodeN where the new objectO belongs. IfN is not full then just attach it toN. IfN is full then invoke a method to splitN. The algorithm is as follows:

Algorithm Insert  Input: NodeN of M-TreeMT,Entry $O_{n}$   Output: A new instance ofMT containing all entries in originalMT plus $O_{n}$

 $N_{e}\gets N$ 's routing objects or objectsifN is not a leafthen  {       /* Look for entries that the new object fits into */let $N_{in}$  be routing objects from $N_{e}$ 's set of routing objects $N_{RO}$ such that $d(O_{r},O_{n})\leq r(O_{r})$ if $N_{in}$  is not emptythen       {          /* If there are one or more entry, then look for an entry such that is closer to the new object */ $O_{r}^{*}\gets \min _{O_{r}\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 */ $O_{r}^{*}\gets \min _{O_{r}\in N_{in}}d(O_{r},O_{n})-r(O_{r})$           /* Upgrade the new radii of the entry */ $r(O_{r}^{*})\gets d(O_{r}^{*},O_{n})$        }       /* Continue inserting in the next level */return insert( $T(O_{r}^{*}),O_{n}$ );else  {       /* If the node has capacity then just insert the new object */ifN is not fullthen       {store( $N,O_{n}$ ) }       /* The node is at full capacity, then it is needed to do a new split in this level */else       {split( $N,O_{n}$ ) }  }

"←" denotesassignment. For instance, "largest ←item" means that the value oflargest changes to the value ofitem.
"return" terminates the algorithm and outputs the following value.

Split

[edit]

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

Algorithm Split  Input: NodeN of M-TreeMT,Entry $O_{n}$   Output: A new instance ofMT containing a new partition.

  /* The new routing objects are now all those in the node plus the new routing object */  let beNN entries of $N\cup O$ ifN is not the rootthen  {     /*Get the parent node and the parent routing object*/let $O_{p}$  be the parent routing object ofNlet $N_{p}$  be the parent node ofN  }  /* This node will contain part of the objects of the node to be split */  Create a new nodeN'  /* Promote two routing objects from the node to be split, to be new routing objects */  Create new objects $O_{p1}$  and $O_{p2}$ .  Promote( $N,O_{p1},O_{p2}$ )  /* Choose which objects from the node being split will act as new routing objects */  Partition( $N,O_{p1},O_{p2},N_{1},N_{2}$ )  /* Store entries in each new routing object */Store $N_{1}$ 's entries inN and $N_{2}$ 's entries inN'ifN is the current rootthen  {      /* Create a new node and set it as new root and store the new routing objects */Create a new root node $N_{p}$ Store $O_{p1}$  and $O_{p2}$  in $N_{p}$   }else  {      /* Now use the parent routing object to store one of the new objects */Replace entry $O_{p}$  with entry $O_{p1}$  in $N_{p}$ if $N_{p}$  is no fullthen      {          /* The second routing object is stored in the parent only if it has free capacity */Store $O_{p2}$  in $N_{p}$       }else      {           /*If there is no free capacity then split the level up*/split( $N_{p},O_{p2}$ )      }  }

"←" denotesassignment. For instance, "largest ←item" means that the value oflargest changes to the value ofitem.
"return" terminates the algorithm and outputs the following value.

M-tree queries

[edit]

Range query

[edit]

A range query is where a minimum similarity/maximum distance value is specified. For a given query object⁠ $Q\in D$ ⁠ and a maximum search distance⁠ $r(Q)$ ⁠, the range queryrange(Q, r(Q)) selects all the indexed objects⁠ $O_{j}$ ⁠ such that⁠ $d(O_{j},Q)\leq r(Q)$ ⁠.^[2]

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

Algorithm RangeSearchInput: NodeN of M-Tree MT,Q: query object, $r(Q)$ : search radius

Output: all the DB objectssuch that $d(Oj,Q)\leq r(Q)$

{let $O_{p}$ be the parent object of nodeN;ifNis not a leafthen {for eachentry( $O_{r}$ )inNdo {if $|d(O_{p},Q)-d(O_{r},O_{p})|\leq r(Q)+r(O_{r})$ then {Compute $d(O_{r},Q)$ ;if $d(O_{r},Q)\leq r(Q)+r(O_{r})$ thenRangeSearch(*ptr( $T(O_{r}$ )),Q, $r(Q)$ );           }    }  }else {for eachentry( $O_{j}$ )inNdo {if $|d(O_{p},Q)-d(O_{j},O_{p})|\leq r(Q)$ then {Compute $d(O_{j},Q)$ ;if $d(O_{j},Q)$  ≤ $r(Q)$ thenadd $oid(O_{j})$  to the result;          }    }  }}

"←" denotesassignment. For instance, "largest ←item" means that the value oflargest changes to the value ofitem.
"return" terminates the algorithm and outputs the following value.

$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-NN queries

[edit]

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 anintegerk ≥ 1, thek-NN query NN(Q, k) selects thek indexed objects which have the shortest distance from Q, according to the distance function d.^[2]

References

[edit]

^Ciaccia, Paolo; Patella, Marco; Zezula, Pavel (1997)."M-tree An Efficient Access Method for Similarity Search in Metric Spaces"(PDF).Proceedings of the 23rd VLDB Conference Athens, Greece, 1997. IBM Almaden Research Center: Very Large Databases Endowment Inc. pp. 426–435. p426. Retrieved2010-09-07.
^^a ^bP. Ciaccia; M. Patella; F. Rabitti; P. Zezula."Indexing Metric Spaces with M-tree"(PDF).Department of Computer Science and Engineering. University of Bologna. p. 3. Retrieved19 November 2013.

v t e Tree data structures
Search trees (dynamic sets, associative arrays)	2–3 2–3–4 AA (a,b) AVL B K-Dimensional B+ B* B^x Binary search Optimal Self-balancing Dancing HTree Interval Order statistic Palindrome (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal d-ary Fibonacci Leftist Pairing Skew binomial Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicitk-d) M Metric MVP Octree PH Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top