度量空间一种自底向上索引树构造算法
A Bottom-Up Distance-Based Index Tree for Metric Space
-
摘要: 在多媒体或复杂对象数据库中，相似性搜索是一种非常重要的操作，这些操作一般可以归结为度量空间的相似性查询.提出一种新的度量空间索引数据结构(bu-tree)，它是基于自底向上的分层聚类来构造索引结构，而传统的度量空间数据结构大部分是基于自顶向下构造的方法.相对于传统的构造方法，bu-tree可以在更小的索引半径内包含更多的对象，这样有利于查询的筛选.给出了bu-tree的构造算法以及相应的范围查询算法.实验表明，bu-tree的性能好于sa-tree，特别是在度量空间不是均匀分布或者查询具有较低的选择度情况下.Abstract: 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.
-
Keywords:
- metric space /
- index tree /
- similarity search
-
计量
- 文章访问数: 643
- HTML全文浏览量: 0
- PDF下载量: 666
下载:
