Tree-based indexing methods for similarity search in metric and nonmetric spaces

Title: Tree-based Indexing Methods for Similarity Search in Metric and Nonmetric Spaces Author: Mgr. Jakub Lokoč Department: Department of Software Engineering Faculty of Mathematics and Physics Charles University in Prague Supervisor: Doc. RNDr. Tomáš Skopal, Ph.D. Author's e-mail address: lokoc@ksi.mff.cuni.cz Supervisor's e-mail address: skopal@ksi.mff.cuni.cz Abstract: 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 sev- eral 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 con- struction 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 im- portant dynamic metric access method suitable for management of large collections of unstructured data. Moreover, all the improvements can be..