NA-Trees: A Dynamic Index for Spatial Data *

In non-standard database applications, such as geographic information processing or CAD/CAM, methods of access are required that support efficient manipulation of multidimensional geometric objects on secondary storage. Spatial data consists of spatial objects made up of points, lines, regions, rectangles, surfaces, volumes, and even data of higher dimension. Being able to respond to spatial queries in a flexible manner places a premium on the appropriate representation of the spatial data. In order to be able to deal with proximity queries, an efficient spatial indexing strategy is needed. In this paper, we consider the problem of retrieving spatial data via exact match queries and range queries from a large, dynamic index, where an exact match query means finding the specific data object in a spatial database and a range query means reporting all data objects which are located in a specific range. By large, we mean that most of the index must be stored in secondary storage. By dynamic, we mean that insertions and deletions are intermixed with queries, so that the index cannot be built beforehand. A new data structure, a Nine-Areas tree (denoted NA-tree), is shown to be a solution to this problem. An NA-tree is designed for paged secondary storage to minimize the number of disk accesses during a tree search. From our simulation, we show that our NA-tree has a lower search cost (in terms of number of visited nodes) than the R-tree, R +-tree, or R *-tree. Keywords: exact match queries, range queries, R-trees, R +-trees, R *-trees, spatial index 1.