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.