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.:
MT *tree=new MT;
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.
Objects can be inserted in the tree one by one or using a bulk-loading technique.
MT::BulkLoadmethod. 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.
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.
MT::RangeSearchmethod 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
MT::TopSearchmethod. Given a
TopQuerywith 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.
MTcursorclass. Then, it is sufficient to repeatedly send the
Next()message to the so-created
MTcursorobject 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
The library includes three integer values,
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.