Indexing in Spatial Databases

Spatial information processing has been a focus of research in the past decade. In spatial databases, data are associated with spatial coordinates and extents, and are retrieved based on spatial proximity. A formidable number of spatial indexes have been proposed to facilitate spatial data retrieval. In this paper, we examine various spatial indexes proposed in the literature and present a taxonomy on them. Each class of indexing structures is reviewed in two steps: first, the index structure is described; second, the strengths and weaknesses are identified. The paper may be used as a guideline in designing new indexing structures and serves as a basis in determining the suitability of a particular class of indexes for specific applications