Spatial searching in geometric databases

A principle is presented for transforming suitable index structures for points into index structures for k-dimensional intervals. In many applications, these intervals serve as simple geometric keys for nonzero-size objects. The transformation fully preserves the advantages of the selected index structure for points, such as efficient update and retrieval operations, especially range queries, as well as high storage space utilization. The authors have implemented an index structure for rectangles based on the grid file. A performance evaluation with geographic data shows highly encouraging results