Indexing Metric Spaces with M-Tree
Indexing Metric Spaces with M-Tree
复制标题
DOI：
--
复制
发表时间：
1997
影响因子：
4.4
通讯作者：
P. Ciaccia;M. Patella;F. Rabitti;P. Zezula
中科院分区：
文献类型：
--
作者：
P. Ciaccia;M. Patella;F. Rabitti;P. Zezula
M-树是一种适用于索引一般度量空间的动态访问方法，其中用于计算任意两个对象之间的距离的函数满足正性、对称性和三角不等式假设。M树设计满足了多媒体应用的典型要求，其中使用复杂特征对对象进行索引，并且相似性查询可能需要应用耗时的距离函数。本文描述了M-树的基本搜索和管理算法，介绍了几种启发式分裂策略，并在考虑I/O和CPU开销的情况下对它们进行了实验评估。结果还表明，在高维向量空间上，M-树比R-∗-树具有更好的性能。
M-tree is a dynamic access method suitable to index generic “metric spaces”, where the function used to compute the distance between any two objects satisfies the positivity, symmetry, and triangle inequality postulates. The M-tree design fulfills typical requirements of multimedia applications, where objects are indexed using complex features, and similarity queries can require application of time-consuming distance functions. In this paper we describe the basic search and management algorithms of M-tree, introduce several heuristic split policies, and experimentally evaluate them, considering both I/O and CPU costs. Results also show that M-tree performs better than R∗-tree on highdimensional vector spaces.