Computer Science Department
School of Computer Science, Carnegie Mellon University


Slim-trees: High Performance Metric Trees
Minimizing Overlap Between Nodes

Caetano Traina, Jr.*, Agma Traina*, Bernhard Seeger**, Christos Faloutsos

October 1999

Keywords: Metric databases, metric access methods, index structures, multimedia databases

In this paper we present the Slim-tree, a dynamic tree for organizing metric datasets in pages of fixed size. The Slim-tree uses the "fat-factor" which provides a simple way to quantify the degree of overlap between the nodes in a metric tree. It is well-known that the degree of overlap directly affects the query performance of index structures. There are many suggestions to reduce overlap in multi-dimensional index structures, but the Slim-tree is the first metric structure explicitly designed to reduce the degree of overlap.

Moreover, we present new algorithms for inserting objects and splitting nodes. The new insertion algorithm leads to a tree with high storage utilization and improved query performance, whereas the new split algorithm runs considerably faster than previous ones, generally without sacrificing search performance. Results obtained from experiments with real-world datasets show that the new algorithms of the Slim-tree consistently lead to performance improvements. For range queries, we observed improvements up to a factor of 35%.

19 pages

*Department of Computer Science, University of Sao Paulo at Sao Carlos, Brazil
**Fachbereich Mathematik und Informatik, Universitaet Marburg, Germany

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by