U de C - logo

SPATIAL DATABASES

diicc - logo

Storage Methods > Structures > Indexing

To speed up spatial selection (as well as other operations such as spatial joins, Ö)
It organizes space and objects in a some way.
Two main approaches:
  • Dedicated spatial data structures (e.g. R-tree)
  • Spatial objects mapped onto a 1-D space to use standard indexing techniques (e.g. B-tree)

A fundamental idea: use of approximations of geometry as keys

  • Object (e.g. bounding box)
  • Grid (a geometric entity as a set of cells)

Filtering and refining strategy for query processing:

  • Filter: returns a set of candidate object which is a superset of the objects fulfilling a predicate
  • Refine: for each candidate, the exact geometry is checked

 

Access methods are concerned with offering operations such as insert,delete, and member to manage the data set as such. In eddition, important spatial queries to be supported are:

  • Point query: find all rectangles containing a point.
  • Range query: find all points within a query rectangle.
  • Nearest Neighbor:Find the point closest to a query.
  • Distance scan: Enumerate points in increasing distance from a query point.
  • Intersection query: Find all the rectangles intersecting a query rectangle.
  • Containment query: Find all the rectangles completely within a query rectangle
  • Spatial join query:Find all pairs of rectangles that overlap each other.

 

 


Valid HTML 4.0! Valid CSS!