# Projects

## M-tree

You are not Member of this Project.
Project Owner : vani.R
Created Date : Thu, 15/03/2012 - 13:09
Project Description :

### Components

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

1. Root.
1. Routing object O.
3. A set of Nodes or (exclusive) Leafs.
2. Node.
1. Routing object Or.
3. Distance from this node to its parent Op.
4. A set of Nodes or (exclusive) Leafs.
3. Leaf.
1. Routing object O.
3. Distance from this leaf to its parent Op.
4. Objects.
4. Objects.
1. Feature value (usually a d-dimensional vector).

### Insert

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

	Algorithm Insert
Input: Node 
$N$
	of M-Tree
$MT$
	, Entry
$O_{n}$
	Output: A new instance of
$MT$
	containing all entries in original
$MT$
	plus
$O_{n}$


$N_{e}$
	← Entries of node
$N$
	if
$N$
	is not a leaf then
{
/*Look for entries that the new object fits into*/
let 
$N_{in}$
	be entries such that
$d(O_{r}, O_{n}) <= r(O_{r})$
	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*/
let be 
$O_{r}^{*} \in N_{in}$
	such that
$d(O_{r}^{*}, O_{n})$
	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 
$O_{r}^{*} \in N_{in}$
	such that
$d(O_{r}^{*}, O_{n}) - r(O_{r})$
	is minimum

$r(O_{r}^{*})$
	=
$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*/
if 
$N$
	is not full then
{  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}$
	) }
}



### Split

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

		Algorithm Split
Input: Node 
$N$
		of M-Tree
$MT$
		, Entry
$O_{n}$
		Output: A new instance of
$MT$
		containing a new partition.

		/*The new routing objects are now all those in the node plus the new routing object*/
let be 
$NN$
		entries of
$N \cup O$
		if
$N$
		is not the root then
{
/*Get the parent node and the parent routing object*/
let 
$O_{p}$
		be the parent routing object of
$N$
		let
$N_{p}$
		be the parent node of
$N$
		}
/*This node will contain part of the objects of the node to be split*/
Create a new node 
$N'$
		/*Promote two routing objects from the node to be split, to be new routing objects*/
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 in
$N$
		and
$N_{2}$
		's entries in
$N'$
		if
$N$
		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 
$N_{p}$
		Store
$O_{p1}$
		and
$O_{p2}$
		in
$N_{p}$
		}
else
{
/*Now use the parent rouing object to store one of the new objects*/
Replace entry 
$O_{p}$
		with entry
$O_{p1}$
		in
$N_{p}$
		if
$N_{p}$
		is no full then
{
/*The second routinb 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}$
		)
}
}
You are not authorized to access this content.
You are not authorized to access this content.
You are not authorized to access this content.
You are not authorized to access this content.
You are not authorized to access this content.