Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]


Journal of Information Science and Engineering, Vol.19 No.1, pp.103-139 (January 2003)

NA-Trees: A Dynamic Index for Spatial Data*

Ye-In Chang, Cheng-Huang Liao+ and Hue-Ling Chen
Department of Computer Science and Engineering
+Department of Applied Mathematics
National Sun Yat-Sen University
Kaohsiung, 804 Taiwan

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

Full Text () Retrieve PDF document (200301_07.pdf)

Received September 1, 2000; revised April 18, 2001; accepted January 25, 2002.
Communicated by Ming-Syan Chen.
* This research was supported in part by the National Science Council of Republic of China under Grant No. NSC-88-0408-E-110-004.