Font Size: a A A

Spatial Index System For Spatial Database Engine

Posted on:2003-09-03Degree:MasterType:Thesis
Country:ChinaCandidate:Z H ChenFull Text:PDF
GTID:2168360062486112Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
While relational database can store spatial objects's data, it does not support efficient access to spatial objects. The multi-dimensional aspect of spatial data makes incompatible with nomal index in relational database. Search key in normal index is one-dimention-based, and is only suitable for indexing one dimentional data. Each dimention of spatial data is not in precedence to other, so special index is needed to support spatial data, which leads to the introduction of spatial index. Spatial index utilizes some kind of spatial relationship to organize data entries, with each key value seen as a point or region in a multi-dimensional space.Spatial index is a indispensable part of spatial database, and can dramatically improve efficiency when doing a spatial query. Demands for spatial index directly come from spatial methods. In spatial database, spatial methods are implemented in two steps: first is filter step, in which spatial object's number is reduced through spatial index. Second is refinement step, in which spatial objects resulted from filter step are subjected to exacted computation. We summarize that spatial index system should provides three kinds of spatial query, they are, spatial range query, nearest neighbor query, spatial join query. Given a query window, spatial range query finds all spatial objects that might conform to certain spatial relationship with the query window. Nearest neighbor query finds spatial object nearest to given point. Spatial join query always involves two or more than two map layers.In this paper, we focus on the structure of R-tree and BucketFile, and the algorithm of three kinds of spatial queries. The basic type of spatial object includes point, polygon and line. R-tree primarily indexes on point and polygon objects. BucketFile only indexes on line objects. R-tree, like B+ tree, is dynamic balanced tree, the search key is based on spatial object's minimum bounding rectangle. Spatial object's minimum bounding rectangle approximately reflects the spatial characters of spatial objects, which speeds the search process. The back idea of BucketFile utilizes space-filling curves to index spatial objects. BucketFile chooses Z-ordering curves, because it's numbering make regions of continuous number reflects their spatial proximity.
Keywords/Search Tags:spatial index, spatial query, R-tree, BucketFile
PDF Full Text Request
Related items