The M-tree turned 27 this year, since it was first published in 1997, at SEBD [ 5] and VLDB [6]. Diferently from the likes of Jim Morrison, Jimi Hendrix, and Amy Winehouse, it is still alive and kicking, receiving dozens of downloads and citations every year.1 In this paper, we ofer a quick overview of the context in which the M-tree was created and show how it helped starting a whole family of metric trees.
CEUR
ceur-ws.org
• an eficient bulk loading technique [
The two original papers were seminal in generating a whole family of metric access methods, sharing the general M-tree structure. Besides the already cited M2-tree and QIC-M-tree, several techniques have been proposed to improve the search performance of M-tree, among which the slim-tree [15], the PM-tree [16], the M+-tree [17], the BM+-tree [18], and the M∗-tree [19]. Finally, the NM-tree [20] is able to deal with distance functions that do not satisfy the metric postulates, in particular the triangle inequality.
In our view, one of the reasons for M-tree success is the fact that, since the very beginning, its source code has been freely available for research purposes at http://www-db.disi.unibo.it/Mtree/. The code of the original M-tree implementation was written in C++ and it is based on the GiST library [21]. A parallel version was presented in [22]. M-tree is now also available, among others, in PostgreSQL, again exploiting GiST [23], as a plugin for the Secondo DBMS (https:// secondo-database.github.io/content_plugins.html) and the ELKI data mining environment (https: //elki-project.github.io/), and in the SurrealDB multi-model database (https://surrealdb.com/). It is finally interesting to note that, in a conference held exactly on the same days as VLDB 1997, a homonymous abstract data type, generalizing a quadtree for parallel adaptive computations, was proposed [24]: such data structure however did not stand the test of time, rapidly fading into oblivion. [9] P. Ciaccia, M. Patella, and P. Zezula. Processing Complex Similarity Queries with Distance
Based Access Methods. EDBT 1998: 9–23. [10] P. Ciaccia, A. Nanni, and M. Patella. A Query-sensitive Cost Model for Similarity Queries with M-Tree. ADC’99: 65–76. [11] P. Ciaccia and M. Patella. PAC Nearest Neighbor Queries: Using the Distance Distribution for Searching in High-Dimensional Metric Spaces. SEBD 1999: 259–273. [12] P. Ciaccia and M. Patella. PAC Nearest Neighbor Queries: Approximate and Controlled
Search in High-Dimensional and Metric Spaces. ICDE 2000: 244–255. [13] P. Ciaccia and M. Patella. The M2-tree: Processing Complex Multi-Feature Queries with
Just One Index. DELOS 2000. [14] P. Ciaccia and M. Patella. Searching in Metric Spaces with User-Defined and Approximate
Distances. ACM TODS 27(4): 398–437 (2002). [15] C. Traina, A.J.M. Traina, B. Seeger, and C. Faloutsos. Slim-Trees: High Performance Metric
Trees Minimizing Overlap Between Nodes. EDBT ’00: 51–-65. [16] T. Skopal, J. Pokorný and V. Snasel. PM-Tree: Pivoting Metric Tree for Similarity Search in
Multimedia Databases. ADBIS 2004: 803–815. [17] X. Zhou, G. Wang, J.X. Yu, and G. Yu. M+-Tree: A New Dynamical Multidimensional Index
For Metric Spaces. ADC’03: 161–-168. [18] X. Zhou, G. Wang, X. Zhou, and G. Yu. BM+-Tree: A Hyperplane-Based Index Method for
High-Dimensional Metric Spaces. DASFAA’05: 398.–409. [19] T. Skopal and D. Hoksza. Improving the Performance of M-Tree Family by Nearest
Neighbor Graphs. ADBIS 2007: 172–188. [20] T. Skopal and J. Lokoč. NM-Tree: Flexible Approximate Similarity Search in Metric and
Non-Metric Spaces. DEXA 2008: 312–325. [21] J.M. Hellerstein, J.F. Naughton and A. Pfefer. Generalized Search Trees for Database
Systems. VLDB 1995: 562–573. [22] P. Zezula, P. Savino, F. Rabitti, G. Amato, and P. Ciaccia, Processing M-trees with Parallel
Resources, RIDE 1998: 147–154. [23] I. Donkó, J. Szalai-Gindl, G. Gombos, and A. Kiss. An Implementation of the M-Tree Index
Structure for PostgreSQL Using GiST. Informatics’2019: 189–194. [24] Q. Wu, A.J. Field, and P.H.J. Kelly. M-Tree: A Parallel Abstract Data Type for Block-Irregular Adaptive Applications. Euro-Par’97: 638–649.