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

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

作　　者：刘兵[1] 严和平[1] 段江娇[1] 汪卫[1] 施伯乐[1] 

机构地区：[1]复旦大学计算机与信息技术系,上海200433

出　　处：《计算机研究与发展》2006年第9期1651-1657,共7页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60303008;60403018);国家"八六三"高技术研究发展计划基金项目(2002AA4Z3430)

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

关 键 词：度量空间 索引树 相似性搜索 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]