R-Trees: A Dynamic Index Structure for Spatial Searching.

Spatial data objects often cover areas in multi-dimensional spaces and are not well represented by point locations. For example, map objects like countries, census tracts etc. occupy regions of non-zero size in two dimensions. A common operation on spatial data is to search for all objects in an area. An example would be to find all the countries that have land within 20 miles of a particular point. This kind of spatial search occurs frequently in computer aided design CAD and geo-data applications. In such applications it is important to be able to retrieve objects efficiently according to their spatial location. A number of structures have been proposed for handling multi-dimensional point data, and a survey of methods can be found. Cell methods are not good for dynamic structures because the cell boundaries must be decided in advance. Quad trees and k-d trees do not take paging of secondary memory into account. K-D-B trees are designed for paged memory but are only useful for point data. The use of index intervals has been suggested but this method cannot be used on multiple dimensions. Corner stitching is an example of a structure for two-dimensional spatial searching suitable for data objects of non zero size, but is assumes homogeneous primary memory and is not efficient for random searches in very large collections of data. Grid files handle non-point data by mapping each object to a point in a higher-dimensional space. This paper describes an alternative structure called an R-tree which represents data objects by intervals in several dimensions.