An Efficient Access Method for Spatial Databases

Abstract

We present a new spatial access method that allows the directory to grow almost linearly with number of insertions, ieerspective of tje data distribution. Our method can be seen as a comprise of tje Quad tree and the grid file. Because the grid file decreases the performance for highly correlated data, our method is designed to organize such data very efficiently. Such rebustness in the design is achieved through the use of a hierarchical directory tree. In our method, the number of disk accesses required to reconstruct the whole directory tree is bounded by O(N X log(N)), where N is the number of points in the database.Reporting on experiments conducted according to the standardized testbed designed by Krieqel et al. to compare multidimensional access methods under arbitrary data distributions and various types of queries, we found that our method outperformed the other method under most conditions.