IBM T.J. Watson Research Center, Yorktown Heights, New York, United States Massachusetts Institute of Technology, Cambridge, Massachusetts, United States
Copyright 1997 INIST-CNRS CC BY 4.0 Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Sciences of information and communication. Documentation
FRANCIS
Accession Number:
edscal.2731342
Database:
PASCAL Archive
Weitere Informationen
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.
