M-Tree

Overview

M-tree is a dynamic tree. Fig. 1 shows an M-tree example. An intermediate (i.e., a non-leaf) entry e in a root node (e.g., N₀) or a non-leaf node (e.g., N₁, N₂) records the following. (i) A routing object e.RO that is a selected object in the subtree ST_e of e. (ii) A covering radius e.r that is the maximum distance between e.RO and the objects in ST_e. (iii) A parent distance e.PD that equals the distance from e to the routing object of its parent entry. Since a root entry e (e.g., e₆) has no parent entry, e.PD = ∞. (iv) An identifier e.ptr that points to the root node of ST_e. In contrast, a leaf entry (i.e., a data object) o in a leaf node (e.g., N₃, N₄, N₅, N₆) records the following. (i) An object o_j that stores the detailed information of o. (ii) An identifier oid that represents o’s identifier. (iii) A parent distance o.PD that equals the distance from o to the routing object of o’s parent entry.

Code Usage

The code can be download from M-tree Project provided by the authors of M-tree.