1998
@article{GaG1998,
vgclass = {refpap},
author = {Volker Gaede and Oliver G\"{u}nther},
title = {Multidimensional access methods},
journal = {ACM Computing Surveys},
volume = {30},
number = {2},
pages = {170--231},
month = {June},
year = {1998},
url = {http://doi.acm.org/10.1145/280277.280279},
abstract = {Search operations in databases require special support at
the physical level. This is true for conventional databases as well as
spatial databases, where typical search operations include the point
query (find all objects that contain a given search point) and the
region query (find all objects that overlap a given search region).
More than ten years of spatial database research have resulted in a
great variety of multidimensional access methods to support such
operations. We give an overview 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 second part of the paper is devoted to spatial access
methods to handle extended objects, such as rectangles or polyhedra. We
conclude with a discussion of theoretical and experimental results
concerning the relative performance of various approaches.},
}