Abstract—Nowadays, the appearance of a great number of multimedia data brings the need for more effective methods to manage these data. The multimedia retrieval systems always index these data based on feature vectors, and the index structures such as the R-tree family are used to manage them more efficiently. Slim-down algorithm is used in Slim-tree, and it can improve the disk access number for range queries in average 10%~20% for vector datasets. In this paper, we use Slim-down algorithm in both SS-tree and R-tree index structures, and propose a new structure: Slim SS-tree. Experiment results show that compared with SS-tree, the disk access number of Slim SS-tree for k nearest neighbor search improves by 20%~30% in average for vector datasets of 32 dimensions, and the Slim SS-tree can provide fast query performance as well. But the Slim-down algorithm is not suitable for reducing the intersection of rectangle regions as it does to the sphere regions. It’s not efficient in rectangle node management.
Index Terms—index structure; Slim SS-tree; R-tree; SS-tree; Slim-down; Reinsertion
Lifang Yang, Xianglin Huang, Rui Lv and Hui Lv are with Computer School, Communication University of China, Beijing, China (email: firstname.lastname@example.org).
Cite: Lifang Yang, Xianglin Huang, Rui Lv and Hui Lv, "Slim SS-tree: A New Tree Combined SS-tree With Slim-down Algorithm," International Journal of Computer Theory and Engineering vol. 2, no. 4, pp. 613-618, 2010.