Book Description

The use of index structures can increase the performance of query processing. However, the index structures for standard databases are not suitable for the non-standard database applications such as geographical applications, CAD applications, VLSI designs and image processing. For non-standard databases, we need an index structure which preserves spatial neighborhood. In this thesis, we proposed two new access methods with improved performance: a projection method and a partition method. In the projection method, we project a spatial data object onto each axis. The projection of an object forms an interval in each dimension. Then, we organize the projection intervals in each dimension as a B-tree. To perform a query, we need to search each of the B-trees and find the set of possible candidates for the given query in each dimension. Then we compute the intersections of those possible candidate sets, which is the final result. In the partition method, if an object is not a point, the object is approximated by a bounding rectangle and then the bounding rectangle is transformed into a point in higher dimensions. The transformed points are organized as a directory tree. Instead of using one tree for each dimension like the projection method, the partition method builds up only one directory tree. All queries are performed against this directory tree. After introducing our two methods, we perform several experiments to compare our methods with other methods for spatial databases under arbitrary data distributions and various types of queries.