Publication Details
Title: Multidimensional Access Methods
Author: V. Gaede and O. Günther
Group: ICSI Technical Reports
Date: October 1996
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1996/tr-96-043.pdf
Overview:
Search operations in databases require some special support at the physical level. This is true for conventional databases as well as for 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. This paper gives 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, which are able to manage extended objects (such as rectangles or polyhedra). We conclude with a discussion of theoretical and experimental results concerning the relative performance of the various approaches. Keywords: multidimensional access methods, data structures, spatial databases
Bibliographic Information:
ICSI Technical Report TR-96-043
Bibliographic Reference:
V. Gaede and O. Günther. Multidimensional Access Methods. ICSI Technical Report TR-96-043, October 1996
Author: V. Gaede and O. Günther
Group: ICSI Technical Reports
Date: October 1996
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1996/tr-96-043.pdf
Overview:
Search operations in databases require some special support at the physical level. This is true for conventional databases as well as for 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. This paper gives 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, which are able to manage extended objects (such as rectangles or polyhedra). We conclude with a discussion of theoretical and experimental results concerning the relative performance of the various approaches. Keywords: multidimensional access methods, data structures, spatial databases
Bibliographic Information:
ICSI Technical Report TR-96-043
Bibliographic Reference:
V. Gaede and O. Günther. Multidimensional Access Methods. ICSI Technical Report TR-96-043, October 1996