度量空间一种自底向上索引树构造算法

在多媒体或复杂对象数据库中，相似性搜索是一种非常重要的操作，这些操作一般可以归结为度量空间的相似性查询．提出一种新的度量空间索引数据结构（bu-tree），它是基于自底向上的分层聚类来构造索引结构，而传统的度量空间数据结构大部分是基于自顶向下构造的方法．相对于传统的构造方法，bu-tree可以在更小的索引半径内包含更多的对象，这样有利于查询的筛选．给出了bu-tree的构造算法以及相应的范围查询算法．实验表明，bu-tree的性能好于sa-tree，特别是在度量空间不是均匀分布或者查询具有较低的选择度情况下．

A Bottom-Up Distance-Based Index Tree for Metric Space

Similarity search is of importance in many new database applications. These operations can generally be referred as similarity search in metric space. A new index construction algorithm is proposed for similarity search in metric space. The new data structure, called bu-tree (bottom-up tree), is based on constructing the index tree from bottom-up, rather than the traditional top-down approaches. The construction algorithm of bu-tree and the range search algorithm based on it are given. And the update of bu-tree is also discussed. The experiments show that bu-tree is better than sa-tree in search efficiency, especially when the objects are not uniformly distributed or the query has low selectivity.