Tree-based indexing methods for similarity search in metric and nonmetric spaces
Jakub Lokoč · Digital Repository (National Repository of Grey Literature) · 2010
The M-tree is a well-known indexing method enabling efficient similarity search in metric spaces. Although the M-tree is an aging method nowadays, we believe it still offers an undiscovered potential. We present several approaches and directions that show how the original M-tree algorithms and structure can be improved. To allow more efficient query processing by the M-tree, we propose several new methods of (parallel) M-tree construction that achieve more compact M-tree hierarchies and preserve acceptable construction cost. We also demonstrate that the M-tree can be simply extended to a new indexing method - the NM-tree, which allows efficient nonmetric similarity search by use of the TriGen algorithm. All these experimentally verified improvements show that the M-tree can still be regarded as an important dynamic metric access method suitable for management of large collections of unstructured data. Moreover, all the improvements can be further adopted by M-tree descendants (e.g. the PM-tree), so that the results presented in this thesis open the door for future research in this area.