Technical Report No. 16, August 1989 - Abstract

Andreas Hutflesz, Hans-Werner Six, Peter Widmayer:
Proximity Queries in Geometric Databases

This report is not available in electronic form!

In geometric databases, large sets of objects have to be organized on secondary storage such that geometric operations, especially proximity queries, can be carried out efficiently. For multidimensional points, efficient data structures have been proposed; little is known, however, for non-point objects. We represent a general principle that allows for the composition of data structures for non-point objects from suitable data structures for points. To assess the merits of the principle, we have implemented a data structure for rectangles on the basis of the grid file. A performance evaluation shows that our approach preserves quite well all advantages of the point data structure, such as efficient proximity queries, insert and delete operations, and high storage space utilization.