Library Classes

MT class

This class implements the M-tree index structure; it is a sub-class of the basic GiST class. Objects of the MT class can be created as usual, and linked to a file stored on disk by using the Open method of the GiSTclass, providing the file name. As an example:

MT *tree=new MT;
tree->Open("index.M3");
... // use of the tree
delete tree;

Methods and attributes

• void Create(const char *filename): links a tree to a new file
• void Open(const char *filename): opens an existing tree
• void Insert(const MTentry& entry): inserts an object
• void BulkLoad(MTentry **data, int n, double padFactor, char *name): bulk-loading algorithm
• GiSTlist<MTentry *> RangeSearch(const MTquery& query) const: range search algorithm
• MTentry **TopSearch(const TopQuery& query) const: top (nearest neighbor) search algorithm
• int MaxLevel() const: returns the tree height

Object class

Instances of this class are the objects indexed by the M-tree. This is the only class in the whole project that needs a redefinition according to the application defined by the user.

When the user redefines the Object class, he/she has to provide all the information necessary to compute the distance between two Objects. Attributes of the Object class, therefore, are represented only by such information (e.g. in the vector space example, the only attribute of the Object class is the array of the coordinates).

Besides, a number of methods should be redefined, in order to obtain the desired behavior for the indexed objects.

Methods and attributes

• Object(): default constructor; it should assign default values to all object attributes
• Object(const Object& obj): copy constructor; it should provide a suitable way to copy the values of all attributes from Object obj to Object *this
• Object(char *key): member constructor needed to "uncompress" an Object from the node representation stored on disk; basically, this should perform the inverse operation with respect to the Compress method.
• ~Object(): destructor; it should de-allocate the memory possibly allocated during Object construction
• Object& operator=(const Object& obj): assignment operator; it should basically mimic the code of the destructor and of the copy constructor methods
• int operator==(const Object& obj) const: equality operator; it should return a non-zero value iff the two Objects can be assumed as equal (or equivalent)
• double distance(const Object& other) const: distance method; it is, of course, the basic method for the M-tree index structure
• void Compress(char *key): compression method, which should copy all the attributes of the Object into the key buffer
• int CompressedLength() const: size of the compressed Object, i.e. the sum of the sizes (in bytes) of each attribute as saved in the node representation stored on disk

Other Functions

• double maxDist(): defines the maximum possible value for the distance between two Objects
• int sizeofObject(): returns the size of each compressed Object, in case Objects have all the same size, or 0 if Objects have different size, so that execution of the Object::CompressedLength() method is needed to retrieve it
• Object *Read(): returns an Object as read from standard input
• Object *Read(FILE *fp): returns an Object as read from file fp

MTkey class

This class contains the representation of the metric space region associated to each entry of the M-tree. Since the M-tree uses balls to organize the space, each region is defined by an Object (the center of the region) and a radius.

Methods and attributes

• Object obj: private, indexed Object
• double rmin: private, minimum radius (only used for compatibility with complex applications)
• double rmax: private, maximum radius (i.e. the entry radius)
• double distance: public, distance between obj and the parent obj
• MTkey(): default constructor
• MTkey(const MTkey& k): copy constructor
• GiSTobject *Copy() const: copy operator, returns a new MTkey as a copy of the current one
• ~MTkey(): destructor
• MTkey& operator=(const MTkey& k): copy operator
• int operator==(const MTkey& k) const: equality operator
• int overlap (const MTkey& k) const: overlap operator, indicates if two regions of the metric space overlap
• int contained(const MTkey& k) const: containment operator, indicates if the current region is contained in the given one
• int contains(const MTkey& k) const: containment operator, indicates if the given region is contained in the current one
• MTkey *expand(const MTkey& k): expansion operator, expands the current region in order to accommodate the given region

MTpenalty class

This is a service class which should never be istantiated nor referred by the user. It is a redefinition of the basic Penalty class of GiST and it is used when inserting objects in the M-tree.

MTentry class

Instances of the MTentry class are the entries contained in each node and represent nodes at the next lower level for internal nodes, and objects for leaf nodes.

Methods and attributes

• MTentry(): default constructor
• MTentry(const MTentry& e): copy constructor
• MTentry(const MTkey& k, const GiSTpage p): member constructor
• GiSTobject *Copy() const: copy operator, returns a new MTentry as a copy of the current one

MTfile class

This is a redefinition of the basic GiSTfile class in order to do some book-keeping, like counting disk access requests, etc.

The user can modify the size in bytes of each disk page (through the PageSize method) in order to tailor nodes fanout for his/her application.

Methods and attributes

• int PageSize() const: size of disk pages in bytes

MTnode class

The MTnode class implements the logic for inserting an entry in a node and for node splitting. This is a service class which should never be istantiated nor referred by the user.

MTpred class

This is the base class for predicates supported by M-tree. It is a virtual class and simple predicates are defined by way of the Pred sub-class, whereas complex predicates for the fuzzy language are defined by way of the AndPred, OrPred, and NotPred sub-classes. If the user wishes to define other complex predicates, such as those created by using the "weighted sum" language, he/she has to derive sub-classes from the MTpred class, and to compose predicates using the Pred class.

Methods and attributes

• double distance(const Object& obj) const: pure virtual, distance method

Pred class

Objects of this class are simple predicates, i.e. leaves of the predicate tree. Each Pred contains the reference to a simple Object, and the distance between the predicate and an object is simply computed as the distance between the two Objects.

Methods and attributes

• Pred(const Object& obj): member constructor
• Pred(const Pred& p): copy constructor
• GiSTobject *Copy() const: copy operator
• const Object& obj(): access to private Object member

AndPred class

This class defines the conjunction between two sub-predicates. The semantics of the conjunction is given through the query_language variable, assuming one of the following values:

• FUZZY_STANDARD: fuzzy standard language
• FUZZY_ALGEBRAIC: fuzzy algebraic language

and the two functions:

• double Dist2Sim(double dist): transforms distance values into similarity scores
• double Sim2Dist(double sim): transforms similarity scores into distance values

Methods and attributes

• AndPred(const MTpred *p1, const MTpred *p2): member constructor
• GiSTobject *Copy() const: copy operator
• MTpred *Pred1(): access to private member
• MTpred *Pred2(): access to private member

OrPred class

This class defines the disjunction between two sub-predicates. The semantics of the disjunction is given in the same way of the conjunction.

Methods and attributes

• OrPred(const MTpred *p1, const MTpred *p2): member constructor
• GiSTobject *Copy() const: copy operator
• MTpred *Pred1(): access to private member
• MTpred *Pred2(): access to private member

NotPred class

This class defines the negation of a predicate. The distance between an Object o and a negated predicate p is given as:

Dist2Sim(1-Sim2Dist(p->Pred()->distance(o)))

Methods and attributes

• NotPred(const MTpred *p): member constructor
• GiSTobject *Copy() const: copy operator
• MTpred *Pred(): access to private member

MTquery class

This is the base class for range queries supported by M-tree.

Methods and attributes

• double grade: private, similarity score computed for the currently examined entry with respect to the query predicate
• MTquery(): default constructor
• MTquery(const double g): member constructor
• int Consistent(const MTentry& entry): pure virtual, checks for consistency
• int NonConsistent(const MTentry& entry): pure virtual, checks for non-consistency (useful for negated queries)
• double Grade() const: access to private member grade
• double SetGrade(double p_grade): access to private member grade

SimpleQuery class

This class implements the simple range query. It is used in the MT::RangeSearch() method.

Methods and attributes

• MTpred *pred: private, query predicate
• double radius: private, query radius
• SimpleQuery(const MTpred *p, const double r): member constructor
• SimpleQuery(const SimpleQuery& q): copy constructor
• GiSTobject *Copy() const: copy operator
• double Radius() const: access to private member radius
• void SetRadius(double p_radius): access to private member radius

TopQuery class

This class implements the simple top query. It is used in the MT::TopSearch() method.

Methods and attributes

• MTpred *pred: private, query predicate
• int k: public, number of neighbors
• TopQuery(const MTpred *p, const int n): member constructor
• TopQuery(const TopQuery& q): copy constructor
• GiSTobject *Copy() const: copy operator
• const MTpred *Pred() const: access to private member pred

MTcursor class

This class implements the sorted access for the M-tree index structure.

Methods and attributes

• const MT& tree: the tree the cursor acts upon
• MTpred *query: the query predicate
• MTcursor(const MT& tree, const MTpred& query): member constructor
• MTentry *Next(): fetches next result from the queue
• BOOL IsReady() const: returns TRUE iff it is not necessary to fetch nodes to return the next result
• double Bound() const: returns a lower bound on the distance between the query predicate and the next result (without fetching any node)