M-tree Implementation

Creating the Tree

Creating a new M-tree is as easy as saying "new"! In fact, in order to create a new index structure, it is sufficient to instantiate the MT class, e.g.:

Then, in order to provide persistence to the index, the user has to "link" the MT object to a file on disk, with the MT::Create method if the index has to be created from scratch, or with the MT::Open method if the index is already stored in a file.

Inserting Objects

Objects can be inserted in the tree one by one or using a bulk-loading technique.

• When inserting objects one-by-one, the user has to specify, for each insertion, an entry (representing the object) and an integer number representing the identifier of the object, which should be unique in the data-set. A simple insertion could be performed by way of the MT::Insert method.
• The bulk-loading algorithm is implemented by the MT::BulkLoad method. This requires the entire data-set to be known in advance. The user could also specify a padding factor in order to leave space inside nodes to accommodate subsequent insertions.

Searching the M-tree

The M-tree can be searched using nearest neighbors and range queries, even in a complex environment where query predicates are expressed as conjunctions, disjunctions, and negations of simple predicates. Moreover, a sorted access to the tree is also provided, where indexed objects are returned one by one sorted by increasing distance to the query predicate.

• The MT::RangeSearch method implements the range search algorithm: when called for the tree with an arbitrarily complex query predicate, it recursively descends the tree, returning a list containing all entries that are consistent with (i.e. satisfy) the query predicate. Returned entries contain the distance between the entry object and the query predicate as the maximum radius of the entry (accessible through the MTentry::maxradius method).
• The k-NN search algorithm is implemented in the MT::TopSearch method. Given a TopQuery with an arbitrarily complex predicate, the algorithm returns an array containing the k entries nearest to the query predicate, sorted by increasing distance. The distance between each entry and the query predicate is returned as the maximum radius of each entry.
• The sorted access to a tree with respect to an arbitrarily complex predicate is performed by creating an instance of the MTcursor class. Then, it is sufficient to repeatedly send the Next() message to the so-created MTcursor object to retrieve, one-by-one, all the indexed objects sorted in increasing order of distance with respect to the predicate. Once the user is satisfied with the result, he/she can interrupt the sorted access by destroying the MTcursor object.

Performance Evaluation

The library includes three integer values, compdists, IOread, and IOwrite, to keep track of CPU and I/O costs for performance evaluation. More precisely, every time a distance is computed (i.e. the method Object::distance is called), the value of compdists is increased by 1; every time a node is read from disk (through the method MTfile::Read), the value of IOread is increased by 1; every time a node is written on disk (through the method MTfile::Write), the value of IOwrite is increased by 1.