DESIGN AND EVALUATION OF ACCESS METHOD FOR MULTIDIMENSIONAL OBJECTS IN SPATIAL DATABASES

The existing conventional access methods are not suitable to many comp lex applications such as geographic information systems, computer-aide d design, and computer vision. Therefore, it is important to use a hig hly efficient access method for complex applications. In this paper, w e propose a new dynamic access method, called Binary divided Region (B R) tree, for spatial data and then implement search, insertion, deleti on, and splitting algorithms used for the BR tree. The proposed access method is compared with the two representative spatial access methods , R-tree and R+-tree, through performance results from analytical stud y and simulation approach for a VLSI data. For search, when the size o f a user-specified rectangular region, called query window, is relativ ely small, BR tree produces the best performance with respect to the n umber of disk accesses since it generates the smallest number of nodes and avoids overlapping of rectangles. For insertion, BR tree achieves up to 20 percent saving in the amount of storage over R-tree and R+-t ree since it does not need the values of coordinates in representing a region. Also, BR tree achieves up to 60 percent saving in insertion t ime over R-tree and R+-tree since it does not require the reorganizati on of tree.