M-tree Features

In order to index objects from a generic metric space, the user has only to supply the description of object features to be indexed and a way to compute a distance d between such features (such distance should be a metric, thus satisfying the positivity, symmetry, and triangle inequality postulates).

Objects can be inserted into the M-tree one by one or using a bulk-loading technique (in case that all the objects to be indexed are known at the time of index construction). Note that bulk-loading the tree is only possible if the index is to be created from scratch (i.e. bulk-merging is not available).

When inserting objects the user could specify both the minimum utilization of tree nodes and the policy to be applied when a node is to be split (split policies are described in the original paper). On the other hand, when using the bulk-loading technique, the user could specify both a minimum and a maximum node utilization (in case he/she wants to leave room in tree nodes to accommodate subsequent insertions).

Object deletion is not supported yet by M-tree due to a bug in the original GiST library 0.9.

The M-tree offers three different ways to search through indexed objects:

Range query
For a range query, the user has to specify a query object q and a query radius r. The tree, then, returns all those indexed objects o whose distance d from q is not higher than r, i.e. for which d(o,q)<= r.
k-nearest neighbors query
For a k-nearest neighbors query, the user specifies the query object q and the number of neighbors k. Then, k indexed objects are returned having the minimum distance d from q.
Sorted access
The sorted access search mode can be viewed as an interactive nearest neighbor search, where the user can iteratively search for the next nearest neighbor of the query object. To this end, the user has only to specify the query object q. Then, each time that the user requests for another object, the tree returns the indexed object which is the nearest to q (according to the distance d) among those not yet returned to the user.