高级检索

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

    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.

       

    /

    返回文章
    返回