Principles of Spatial Data Access and Search

Introduction

One of the few important principles governing the searching algorithm is the partitioning of the search space into regions that are usually, but not necessarily, rectangular in shape. Considered simply, this consists of placing data into uniquely identifiable boxes or cells. These methods are characterized as employing spatial indexing because with each block the only information that is stored is whether or not the block is occupied by the spatial object or part of the object.
Jones (1997) distinguishes two types of space decomposition or partitioning: regular decomposition and object-directed decomposition. Here you will find just a short explanation. They will be discussed in an exhaustive manner in the following units.

Regular decomposition (space driven indexes)

The space is partitioned in a regular or semi-regular manner that is only indirectly related to the objects in the space (“space primary”). The idea of superimposing a regular pattern of cells over the geometric data to be stored has much in common with the raster model of data storage. The main difference between a regular grid and a raster is that rather than the cells being uniform, equivalent to a pixel, they are compartments capable of storing geometric objects.

Regular decomposition

Object-directed decomposition (data driven indexes)

The partitioning of the index space is determined directly by the objects (“object primary”). This technique partitions space by means of the coordinates of individual data points or of the extents or bounding rectangles or geometric objects which are to be stored. There is a multiplicity of object-directed decomposition search methods. The most common are:

Binary tree
R-tree

Object-directed decomposition