Similarity indexing with the SS-tree

Abstract

Efficient indexing of high dimensional feature vectors is important to allow visual information systems and a number other applications to scale up to large databases. We define this problem as "similarity indexing" and describe the fundamental types of "similarity queries" that we believe should be supported. We also propose a new dynamic structure for similarity indexing called the similarity search tree or SS-tree. In nearly every test we performed on high dimensional data, we found that this structure performed better than the R*-tree. Our tests also show that the SS-tree is much better suited for approximate queries than the R*-tree.