MULTIDIMENSIONAL ACCESS METHODS

Search operations in databases require special support at the physical level. This is true for conventional databases as well as spatial dat abases, where typical search operations include the point query (find all objects that contain a given search point) and the region query (f ind all objects that overlap a given search region). More than ten yea rs of spatial database research have resulted in a great variety of mu ltidimensional access methods to support such operations. We give an o verview of that work. After a brief survey of spatial data management in general, we first present the class of point access methods, which are used to search sets of points in two or more dimensions. The secon d part of the paper is devoted to spatial access methods to handle ext ended objects, such as rectangles or polyhedra. We conclude with a dis cussion of theoretical and experimental results concerning the relativ e performance of various approaches.