Node splitting algorithms in tree-structured high-dimensional indexes for similarity search

Content-based searches and retrievals in multimedia and image databases use high-dimensional indexing structures for organizing the features of the objects. Most of those index structures are tree-structured whose nodes have a limit on the number of entries describing the subtrees rooted at those nodes. When index trees are built by repeated insertion of entries, nodes need to be split and the tree balanced accordingly. Node-splitting algorithms eventually determine the final structure of the tree which will have a profound effect on the search performance. This paper presents a comparative study of several node splitting algorithms for a typical high-dimensional indexing structure. The algorithms are implemented and tested on an image database and the results are presented.