Grid (spatial Index) - Grid-based Spatial Indexing

Grid-based Spatial Indexing

In practice, construction of grid-based spatial indexes entails allocation of relevant objects to their position or positions in the grid, then creating an index of object identifiers vs. grid cell identifiers for rapid access. This is an example of a "space-driven" or data independent method, as opposed to "data-driven" or data dependent method, as discussed further in Rigaux et al. (2002)). A grid-based spatial index has the advantage that the structure of the index can be created first, and data added on an ongoing basis without requiring any change to the index structure; indeed, if a common grid is used by disparate data collecting and indexing activities, such indexes can easily be merged from a variety of sources. On the other hand, data driven structures such as R-trees can be more efficient for data storage and speed at search execution time, though they are generally tied to the internal structure of a given data storage system.

The use of such spatial indexes is not limited to digital data; the "index" section of any global or street atlas commonly contains a list of named features (towns, streets, etc.) with associated grid square identifiers, and may be considered a perfectly acceptable example of a spatial index (in this case, typically organised by feature name, though the reverse is conceptually also possible).