Thumbnail
Access Restriction
Open

Author Chang, Ye-In ♦ Liao, Cheng-Huang ♦ Chen, Hue-Ling
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Index Cannot ♦ Nine-areas Tree ♦ Spatial Query ♦ Exact Match Query ♦ Spatial Data ♦ Specific Data ♦ Proximity Query ♦ Dynamic Index ♦ Disk Access ♦ Appropriate Representation ♦ Spatial Index ♦ Visited Node ♦ Support Efficient Manipulation ♦ Spatial Database ♦ Tree Search ♦ Range Query ♦ Secondary Storage ♦ Specific Range ♦ Multidimensional Geometric Object ♦ Efficient Spatial Indexing Strategy ♦ Data Object ♦ Cad Cam ♦ Search Cost ♦ Spatial Data Consists ♦ Flexible Manner Place ♦ Paged Secondary Storage ♦ Non-standard Database Application ♦ New Data Structure ♦ Geographic Information Processing ♦ Spatial Object
Abstract 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.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study