Spatial Access Methods

 

The main problem in design of spatial access methods is that there is no total ordering among the spatial data objects that preserves spatial proximity. Consider, for example, a user wants to find $5$ restaurants closest to her location. One try to answer this query is to build a one-dimensional index that contains the distances of all restaurants from user's location sorted in ascending order. To answer her query, we can return first $5$ entries from the sorted index. However, this index cannot support a query issued by some other user at a different location. In order to answer the query of this new user, we will have to sort all the restaurants again in ascending order of their distances from this user. The difficulty lies in the fact that there is no mapping from multidimensional space into one-dimensional space so that the objects that are close in multidimensional space are also close in the one-dimensional sorted index [GG98].

Another way to answer the queries of above type is to sort each restaurant in two lists. First list ($List_x$ ) contains the restaurants sorted in ascending order on their x-coordinates. The second list ($List_y$ ) may contain them sorted according to their y-coordinates. In order to find $5$ closest restaurants to a point $p$ located at ($p_x,p_y$ ), we may first find few candidates from $List_x$ that are closest to $p_x$ and then we could calculate their actual distance from $p$ by looking their value in $List_y$ . However, this approach can be very in-efficient because a restaurant that is closest to $p$ in x-dimension may be the farthest restaurant in y-dimension. Consider the example of Fig.  where the object closest to $p_1$ is to be found. The objects $p_3$ and $p_4$ are the closest objects to $p_1$ in x and y dimensions, respectively. However, the nearest object in the two-dimensional space is $p_2$ which is not the closest object in any single dimension.

Figure: Difficulty in Finding the Spatial Proximity of Objects

For the reason mentioned above, traditional one-dimensional access methods like B-tree [BM72] and extendible hashing [FNPS79] are not suitable for spatial databases. An excellent survey on multidimensional access methods by Gaede et al. can be found in [GG98]. Gaede et al. describe the requirements that multidimensional access methods should meet, based on the properties of spatial data and their applications.

• Dynamics: Spatial data objects can be inserted and deleted in any order and the spatial access methods should be able to continuously record the changes.
• Secondary/tertiary storage management: Even though the size of main memory is increasing, it is not always possible to store the complete database in main memory. The access methods need to integrate secondary and tertiary storage in seemless manner.
• Broad ranges of supported operations: The access methods should not support only one particular type of operation at the expense of other operations. For example, an access method is not good if insertion of data points into it is efficient but other operations like deletion of the points are slow.
• Independence of the input data and insertion sequence: The access methods should maintain their efficiency even when input data are highly skewed or the insertion sequence is changed.
• Simplicity: Complex access methods are usually difficult to implement and are error-prone thus not suitable for large-scale applications.
• Scalability: The access method should adapt well with the database growth.
• Time efficiency: The access method should provide fast spatial searches.
• Space efficiency: An index should be small in size compared to the data to be addressed and therefore it must guarantee a certain storage utilization.
• Concurrency and recovery: In modern databases, multiple users run operations on databases concurrently. The access methods should provide robust techniques for transaction management without significant performance penalties.
• Minimum impact: The integration of an access method into a database system should have minimum impact on the existing parts of the system.

There have been many spatial access methods proposed in last two decades. Some of the popular spatial indexes are R-tree [Gut84] and its variants(e.g. R*-tree [BKSS90] and $R^+$ -tree [SSH86]), $kd$ -tree [Ben75] and the grid file [NHS84].