Spatial Indexing Structures 
J. KOURIS, E. THEODORIDIS AND A. TSAKALIDIS 
 Computer Engineering & Informatics Department
University of Patras 
26500 Patras
GREECE
Research Academic Computer Technology Institute
61 Riga Feraiou St., 26221 Patras, 
GREECE

Abstract: - In this paper we survey the most well known and widely used indexing structures for handling spatial information using both main memory and secondary media. We focus on the presentation of spatial object indexing structures and then we cite a number of applications that they can be used.   We have paid attention to the variety of queries that each of these structures can answer and their price in computational time and memory space occupation.

Key-Words: - spatial information, data structures, indexing structures, objects, multidimensional access methods.

1   Introduction
The last few decades the emerging area of geographic information systems  have met a remarkable growth providing solutions to a  myriad agricultural, geologic, oceanlogic, navigating, meteorological, seismologic, satellite, military, urban planning   and environmental problems. In these applications physical objects that lie in space  and occupy a certain region are represented with abstract spatial models such as points, lines, rectangles, polygons and  polyhedrons in one, two and higher dimensions respectively. These models are used to simulate physical actions or reactions, to depict in graphical means the objects and to warehouse their position in space in a database.
	     This kind of spatial modeling is often used and in other fields of computer science such as the mechanical and VLSI CAD (computer aided design). The first field usually uses data objects that are three-dimensional solids while the later rely mostly on two-dimensional or layered two-dimensional data. Other systems that make heavy use of spatial data modeling is medical imaging, robotics and mobile network systems. Consult [1] for another listing of possible applications.
	     All the above applications need to have full knowledge about their objects in means of their shape, extent and position is space. Thus there is need of a database storing all this spatial information that is capable to answer certain spatial queries such as “which objects exist in that area” or “which objects intersect/overlap with others” etc.
	     In the remaining of this paper we are going to investigate the special characteristics of spatial data and the variety of spatial queries where encountered (section 2), the indexing structures that efficiently store (in means of memory occupation and update computational time) the data and the queries that each structure answer efficiently (in means of computational time) (section 3). Finally, we are going to expose some conclusions and judging thoughts about them in the last section (section 4).

2   Special Properties of Spatial Data
The spatial data have special characteristics that complicate the design and implementation of indexes on them.
	     First of all spatial data have a complex structure. A spatial object could vary from a single point to a polyhedron or a polygon with several surfaces   and edges. Common relational databases in most cases are not capable to store and handle this variety of forms of spatial data. In addition, spatial data are usually dynamic, which means that quite often update operations occur between query operations. For this case, an index structure has to be kept in a firm form (with bounded their depth) in favor of reasonable search times. Another crucial property is that spatial datasets tend to be extremely large. Consider for example geographic map or a molecular depiction that typically occupy several gigabytes of storage. This fact obligate indexes to be settled on secondary storage devices. Furthermore, there is no standard algebra upon spatial data. In most cases the operations are determined by the nature of the application resulting frequently an very specialized configuration. Finally, many spatial operators are not closed. For example the intersection of two polygons may return a number of points, lines, curved edges and disjoint polygons. This characteristic may produce enormously large answers. In the end of the day a spatial index has to consider all these parameters in order to perform well.
	     On the contrary, to the common dictionary data structures, where the queries (membership, predecessor/successor) are more straightforward, there is need for more complex queries upon spatial datasets. The feature that complicates the scenery a bit is the fact that spatial objects are multidimensional. Thus, there is no way to sort spatial objects in a linear order. This complicates the computation of auxiliary data which are going to be used as branching information at the internal nodes of a search tree, like integers for example in a classical B-tree.  
	     As we mentioned before the queries depend highly on the application but usually the following are observed: exact match query – find all spatial objects with exactly the same spatial extent as the query object; point query – find all the spatial objects that a point stabs; range query – find all spatial objects that have at least on common point with a d-dimensional query window; overlap query – find all spatial objects that have at least on common point with a query object; enclosure query – find all spatial objects that enclose a query object; containment query –  find all spatial objects that are enclosed by a query object; adjacency query –  find all spatial objects that have common boundaries to a query object and finally nearest neighbor query– find all spatial objects that have a minimum distance from a query object. 
	     In [1] Gaede et al. the access methods on spatial data are divided in two categories; the point access methods (PAMs) and the multidimensional access methods (MAMs). The first methods are restricted only to point spatial objects while the later methods are for extended objects such lines, polygons, polyhedra etc. Each of these categories is tackled specially because of the different nature of the data.  	     The indexes in PAMs usually organize the point objects in buckets/clusters. Each of the buckets corresponds to a specific sub-space of the universe space and to a disk page.  Those buckets internally are organized either by hash index structures or by hierarchical data structures or by scheme using both.  A total linear ordering of d-dimensional points is not possible so many heuristic techniques are usually used for placing points that are close in the multidimensional space to the same or very close bucket. For this task often, space-filling curves are used to preserve spatial proximity when ordering multidimensional points in the 1-dimensional space. These methods recommend a total ordering of spatial objects, in which with high probability two points that are close in the original space will be placed close to the total order. See [2] for a detailed presentation of those techniques.  On the other hand hierarchical data structures use ruler to divide the original space into disjoint sub-spaces with a proper rule and use this sub-division to construct brunching information and thus a search tree structure. For example indexes of this category are quad-trees [3] and k-d-trees [4]. 
	     On the other hand, indexes of MAMs handle objects with spatial extent. Because the objects in real applications can have arbitrary shape they are usually represented as objects with more canonical form like rectangles, parallelepipeds. The first way is to map the objects to points. Usually those points are the centers of gravity of the objects or the geometric objects are mapped into higher dimensional space (e.x a rectangle in R2 can be viewed as a point in R4). Then we organize the data with PAMs indexes. The second and most popular approach is to represent a spatial object by the smallest parallelepiped that overlaps it. Methods of this approach usually decompose the space in a hierarchical manner. Objects are stored at the leaves and internal nodes from the root to the leaves recursively decompose the space. The main feature of this method is that for a given query many paths from the root to the leaves may be visited, when the query touch the sub-space of the nodes. Main representatives are R-trees [5] and R*-trees [6].  Another way is to clip the object in a proper manner that produces disjoint sub-spaces at internal nodes and making those queries to follow a single path only. The objects are clipped and stored in many leafs of disjoint sub-spaces. An example of such method exists in R+-trees [7]. Finally, the last approach is to use multiple layers. We partition the space more than one times and each partition consists a layer. Those layers are organized in a proper way, so that regions in the same layer do not overlap. Each layer may use different criterion to partition the space. An object is stored to a region of the lowest possible layer that can store the object without clipping it. Multilayer grid files [8] are using this technique. 

3   Spatial Indexing Structures
In this section, we are going to survey the most important PAMs and MAMs indexing structures. We strictly emphasize to the basic idea behind those structures and to their advantages and disadvantages. 

3.1	Point Indexing Structures 
When the points are placed on one axis then many of the classical main and secondary memory dictionary data structures can be used to organize those one-dimensional points. The most common structures used for this purpose are linear hashing [9], extendible hashing [10] and B-trees [11]. In the extreme case that the data sets fit in main memory any dynamic hashing structure or any balanced tree could be used to handle the points.
	     In the case that points are from a multi-dimension space, suppose d-dimensional, and for the setting of main memory the most used indexing structures are quad-trees [12] and k-d-trees [13]. The quad-trees [12] are rooted trees in which every internal node has four children. Every node in the quad-tree corresponds to a square, when we are on a plane, or in a hyperplane in d-dimensions. If a node w has children, then their corresponding square/hyperplanes are the four quadrants of the square/hyperplane of w. This recursion is applied starting from the root, which corresponds to the entire space until the leaves that correspond to a sub-space containing one point. This basic decomposition method can be applied for geometric objects in the plain in general. Consult [2] for an in-deep presentation of quad-tree and its variants. The and k-d-trees [13], which are binary trees decompose the space but in (d-1)-dimensional hyperplanes. This means that recursively we divide the space in half along to the d possible dimensions until sub-spaces with one point remain (see Fig.1).  

l3

l7

l6

l9

l1

l2

l5

l8

l4

p4

p5

p1

p3

p6

p8

p7

p9

p10

l2

p1

p2

p3

p4

p5

l4

p2

l5

l8

l3

p6

p7

p8

p9

p10

l6

l7

l9

l1

Fig. 1 k-d-tree for points on plane

When the points are not evenly distributed in space then a large number of points can be placed in a specific subtree, leaving the other subtrees lighter. A variation of k-d-tree, the adaptive k-d-tree [14], skips this disadvantage by partitioning recursively the space in two parts, each of them having the same number of points.  
	     In real word applications where the data sets are big enough that usually do not fit in the main memory we rely on disks to store them. In that case, the internal nodes store  branching information and the data are stored in disk blocks. In that setting many close enough points have to form a group that is placed on a single disk block. There are several indexing structures for this setting using the hashing of the hierarchical approach. The grid file [15] sets a d-dimensional orthogonal grid on the space. The grid is not regularly shaped which means that the produced cells do not have all the same size. Each of these cells is placed in a disk block. To speed up the queries the grid, in other words the limits of each cell, are stored in main memory. Each cell sets a pointer to the corresponding disk block. To decrease the number of disk blocks in use, adjacent grid cells can be stored in the same block if their overall size permit such an action. During an insertion if a cell has reached the disk size limits has to been split. If there are several cells in the same physical block then we distribute the cells among the old disk block and a new one. If the cell holds a block by itself then the whole grid directory has to increase and the points of the touched cells have to be reorganized.  See [16] for a theoretical analysis and many of its variants. There are several hashing like schemes like excel [17] and two-level grid file [18] that enhance the primary idea trying to constrain the reorganizations of the grid. Consult [1] for more details.
	     There are also quite a few hierarchical data structures for indexing d-dimensional points. The most popular is the k-d-B-tree [19], which follows the ideas of the adaptive k-d-tree in combination with the B-tree for utilizing secondary memory. Once more hyperplanes are used to divide the space. More than one hyperplanes divide a tree node, depending on the permissible degree of the node, in a corresponding number of disjoint regions. All nodes of the tree correspond to disk pages. A leaf node stores the data points that are located in the respective partition the leaf defines. The k-d-B-tree is perfectly balanced, like the B-tree, guarantying logarithmic worst case I/Os but the storage utilization may be poor. There exist many works that trying to enhance k-d-B-tree or to use ideas, which combine draft decompositions index levels in main memory with coarser level indexes places on disks. Some of them are the LSD-tree[20], the Buddy-tree[21] and the hB-tree[22]. 

3.2 Multi-dimensional Object Indexing Structures 
Contrarily to the point indexing structures, MAM’s indexes have to handle objects with spatial extent and in some cases with arbitrary shape.
	     A first approach can be the mapping of the objects to higher-dimensional space. After the mapping of objects to points in a higher-dimensional space a multi-dimensional point indexing structure can be used. This idea can easily apply when the objects have simple and regular geometrical shapes. For example, a square from a plane can map into a point in the tree-dimensional space. The two coordinates of one corner and the length of its edges are fair enough to describe the square. Those tree values can be the coordinates of point in the tree-dimensional space, which represent the square. For a rectangle, we do the same using points in four-dimensional space. This scheme is getting a bit complicating when the objects are more complex. On way to overcome this difficulty is to approximate the complex objects with regular geometric objects, for example the minimum bounding rectangle, sphere or parallelepiped. Then the mapping to points of higher-dimensional space can proceed. The main disadvantages of this approach, even for evenly scattered objects, is that after the mapping objects that are close in the initial space are placed far away in the new one. This makes difficult for some queries to be answered.
	     The alternative and in many cases most efficient way for dealing with the problem is to use overlapping regions. The key idea of the overlapping regions technique is to allow different data buckets or nodes to correspond to mutually overlapping sub-spaces. The main drawback of this approach is that the existence of overlapping sub-spaces at sibling internal nodes can force a query to search in more than one path from the root to the leaves. Although this fact, practically using heuristics nice performance can achieved.
	     The most known hierarchical structure using this idea is R-tree [23]. R-trees are used to store, instead of the original spatial objects, their minimum bounding d-dimensional rectangles. R-trees, having structure similar to B-trees, are balanced and they ensure efficient storage utilization. R-tree nodes correspond to a disk pages and to a d-dimensional rectangle. At each internal node, the corresponding rectangle bounds the rectangles of all his descendants.  Finally, leaves contain pointers to the indexed data objects.

   O5

O1

O2

O3

O4

O6

O7

O8

O9

O10

O11

O12

Ι1

Ι2

Ι3

Ι4

Ι5

Ι6

Ι7

Ι1

Ι2

Ι6

Ι7

Ι3

Ι4

Ι5

Ο1

Ο2

Ο3

Ο4

Ο7

Ο8

Ο9

Ο5

Ο6

Ο10

Ο11

Ο12

Fig. 2 R-tree

Searching in an R-tree is done in a similar way as in a B-tree. For both point and region queries, the paths where rectangles intersect with the query object are followed. In contrast to the B-tree, the R-tree does not guarantee that traversing one path of the tree is enough when searching for an object, as the bounding rectangles of entries in the same nodes may overlap one another. In the worst case, the search algorithm may have to visit all index pages, in order to answer a query.
	     Concerning the searching efficiency of the R-tree one crucial issue is to minimize the spatial overlap between sibling nodes. There are a couple of heuristic techniques for achieving that.  These ideas are in R+-trees [6] and in R*-trees[7].   R+-trees [6] do not allow the sub-spaces of each internal node to overlap with the sub-space of its sibling nodes. This clipping of the sub-spaces has as an immediate consequence, the creation of much more sub-spaces and thus much more leaves. In addition, an object is assigned to more than one leaves causing a much larger tree structure. In spite that the queries follow a single path for the root to the leaves.
	     The R*-trees[7] follow a different technique to overcome the drawbacks of the R-tree. The sub-space overlapping problem having the R-trees is produced when at updating a node has to split to fit in a disk block. The node is divided according to the sub-spaces of its children. R*-trees  rather to split the nodes insert in the structure from the beginning q (q=approx 30%) objects from the sub-tree of the split node. Another novel approach of the R*-trees is the use of bounding rectangles with equal all their edges (cubes in tree-dimensional space) and the enforcing at each internal node to minimize the overlapping of the sub-spaces along with the perimeter of the bounding rectangles. Experimental studies note that R*-trees can achieve 50% better query times from the common R-trees.

4   Conclusion
In this paper, we have mentioned some of the most common and frequently user spatial indexing structures. Most of these structures may not have guaranteed well worst-case behavior but they gain in simplicity, in understanding and implementing. Experimental studies [1] claim that these structures can be tuned according to the problem and have a very satisfactory behavior in practice. 

Acknowledgments: 
John Kouris would like to thank European Social Fund (ESF), Operational Program for Educational and Vocational Training II (EPEAEK II) and particularly the Program IRAKLEITOS for partial funding the above work.
	     Evangelos Theodoridis would like to thank European Social Fund (ESF), Operational Program for Educational and Vocational Training II (EPEAEK II) and particularly the Program PYTHAGORAS for partial funding the above work.

References:
[1] V. Gaede and O. Gunther, Multidimensional Access Methods, ACM Computing Surveys, Vol.30, No.2, 1998, pp. 170-231.
[2] H. Samet, The Design and Analysis of Spatial Data Structures, Addison Wesley, 1990.
[3] R. Fink and J. Bentley, Quad Trees: a data structure for retrieval of composite keys, Acta Informatica, Vol.4, No.1, 1974, pp. 1-9.
[4] J. Bentley, Multidimensional binary seach trees used for associative searching, Communications of the ACM, Vol.18, No.9, 1975, pp. 509-517.
[5] A. Guttman, R-trees: a dynamic index structure for spatial searching, In proceedings of the ACM SIGMOD International Conference on Management of Data 1984, pp. 47-54.
[6] N. Beckmann, H. Kriegel, R. Schneider and B. Seeger, The R*-tree: An efficient and robust access method for points and rectangles, In proceedings of the ACM SIGMOD International Conference on Management of Data, 1990, pp. 322-331.
[7] T. Sellis, N. Roussopoylos and C. Faloutsos, The R+-tree: A dynamic index for multidimensional objects, In proceedings of the 13th International Conference on Management of Very Large Data Bases, 1987, pp. 507-518.
[8] H. Six and  P. Widmayer, Spatial searching in geometric databases, In proceedings of the 4th International Conference on Data Engineering, 1988, pp. 496-503.
[9] P. Larson, Linear Hashing with partial expansions, In proceedings of the 6th International Conference on Very Large Data Bases Engineering, 1980, pp. 224-232.
[10] R. Fagin, J. Nievergelt, N. Pippenger and R Strong, Extendible hashing: a fast access method for dynamic files, ACM Transactions on Database System, Vol.4, No.3, 1979, pp. 315-344.
[11] R. Bayer and E. McCreight, Organization and maintenance of large ordered indices, Acta Informatica, Vol.1, No.3, 1972, pp. 173-189.
[12] R. Bayer and E. McCreight, Organization and maintenance of large ordered indices, Acta Informatica, Vol.1, No.3, 1972, pp. 173-189.
[13] J. Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, Vol.18, No.9, 1975, pp. 509-517.
[14] J. Bentley and J. Friedman, Data structures for range searching, ACM Computing Surveys, Vol.11, No.4, 1979, pp. 397-409.
[15] J. Nievergelt, H. Hinterberger and K. SSevcik, The grid file: an adaptable symmetric multi-key file structure, ACM Transactions on Database System, Vol.9, No.1, 1984, pp. 38-71.
[16] L. Becker, A new algorithm and a cost model for join processing with the grid file, Phd thesis University of Gesamthochsule, 1992, Germany.
[17] M. Tamminen, The extendible cell method for closest point problems, BIT 22, pp. 27-41.
[18] K. Hinrichs, The grid file system: implementation and case studies of applications, Phd thesis Institute of Informatics ETH, 1985,  Switzerland.
[19] J. Robinson, The k-d-Btree: a search structure for large multidimensional dynamic indexes, In proceedings of the ACM SIGMOD  International Conference on Management of Data, 1981, pp. 10-18.
[20] A. Henrich, H. Six and P. Widmayer, The LSD-tree: spatial access to multidimensional point and non-point objects, In proceedings of the 15th International Conference on Very Large Data Bases, 1989, pp. 45-53.
[21] B. Sieger and H. Kriegel,The buddy-tree: an efficient and robust access method for spatial data base system, In proceedings of the 16th International Conference on Very Large Data Bases, 1990, pp. 590-601.
[22] D. Lomet and B. Salzberg, The HB-tree: a multiattribute indexing method with good guaranteed performance, ACM Transactions on Database System, Vol.15, No.4, 1990, pp. 625-658.
[23] A. Guttman, R-tress: a dynamic index structure for spatial searching, , In proceedings of the ACM SIGMOD  International Conference on Management of Data, 1984, pp. 45-47.