%0 Conference Paper %1 CiacciaEtAl1997 %A Ciaccia, Paolo %A Patella, Marco %A Zezula, Pavel %B VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece %D 1997 %E Jarke, Matthias %E Carey, Michael J. %E Dittrich, Klaus R. %E Lochovsky, Frederick H. %E Loucopoulos, Pericles %E Jeusfeld, Manfred A. %I Morgan Kaufmann %K B_scanpathsimilarity algorithm efficient indexing metric %P 426-435 %T M-tree: An Efficient Access Method for Similarity Search in Metric Spaces %X A new access method, called M-tree, is proposed to organize and search large data sets from a generic "metric space", i.e. where object proximity is only defined by a distance function satisfying the positivity, symmetry, and triangle inequality postulates. We detail algorithms for insertion of objects and split management, which keep the M-tree always balanced - several heuristic split alternatives are considered and experimentally evaluated. Algorithms for similarity (range and k-nearest neighbors) queries are also described. sults from extensive experimentation with a prototype system are reported, considering as the performance criteria the number of page I/O's and the number of distance computa- tions. The results demonstrate that the M-tree indeed extends the domain of applicability beyond the traditional vector spaces, performs reasonably well in high-dimensional data spaces, and scales well in case of growing files. %@ 1-55860-470-7

@inproceedings{CiacciaEtAl1997, abstract = {A new access method, called M-tree, is proposed to organize and search large data sets from a generic "metric space", i.e. where object proximity is only defined by a distance function satisfying the positivity, symmetry, and triangle inequality postulates. We detail algorithms for insertion of objects and split management, which keep the M-tree always balanced - several heuristic split alternatives are considered and experimentally evaluated. Algorithms for similarity (range and k-nearest neighbors) queries are also described. sults from extensive experimentation with a prototype system are reported, considering as the performance criteria the number of page I/O's and the number of distance computa- tions. The results demonstrate that the M-tree indeed extends the domain of applicability beyond the traditional vector spaces, performs reasonably well in high-dimensional data spaces, and scales well in case of growing files. }, added-at = {2007-11-02T15:35:30.000+0100}, author = {Ciaccia, Paolo and Patella, Marco and Zezula, Pavel}, bibsource = {DBLP, http://dblp.uni-trier.de}, biburl = {https://www.bibsonomy.org/bibtex/204dd41fccf5b3b402e1164aa83fda8ca/tmalsburg}, booktitle = {VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece}, description = {VLDB 1997: 426-435}, editor = {Jarke, Matthias and Carey, Michael J. and Dittrich, Klaus R. and Lochovsky, Frederick H. and Loucopoulos, Pericles and Jeusfeld, Manfred A.}, ee = {db/conf/vldb/CiacciaPZ97.html}, interhash = {be29eeedccfe7ff711bc0c1bb1240c66}, intrahash = {04dd41fccf5b3b402e1164aa83fda8ca}, isbn = {1-55860-470-7}, keywords = {B_scanpathsimilarity algorithm efficient indexing metric}, pages = {426-435}, publisher = {Morgan Kaufmann}, timestamp = {2007-11-02T15:35:31.000+0100}, title = {M-tree: An Efficient Access Method for Similarity Search in Metric Spaces}, year = 1997 }