The S-Tree: An Efficient Index for Multidimesional Objects

In this paper we introduce a new multidimensional index called the S-tree. Such indexes are appropriate for a large variety of pictorial databases such as cartography, satellite and medical images. The S-tree discussed in this paper is similar in flavor to the standard R-tree, but accepts mild imbalance in the resulting tree in return for significantly reduced area, overlap and perimeter in the resulting minimum bounding rectangles. In fact, the S-tree is defined in terms of a parameter which governs the degree to which this trade-off is allowed. We develop an efficient packing algorithm based on this parameter. We then analyze the S-tree analytically, giving theoretical bounds on the degree of imbalance of the tree. We also analyze the S-tree experimentally. While the S-tree is extremely effective for static databases, we outline the extension to dynamic databases as well.

By: Charu C. Aggarwal, Joel Wolf, Philip Yu and Marina Epelman (MIT)

Published in: Lecture Notes In Computer Science, volume 1262, (no ), pages 350-73 in 1997

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .