Multi-dimensional range query processing with spatial relations

The processing of multi-dimensional range queries involving spatial relations arises in many application areas including Spatial Databases and GISs. In this paper we show how a variety of three- or four-dimensional queries that correspond to different relations can be processed using spatial data structures. We provide analytical formulas that describe the expected cost of retrieval and test the accuracy of the formulas through extensive experimentation. We also propose alternative methods aimed at the efficient processing of certain queries. The paper concludes by discussing the most suitable data structure for each type of query taking into account the properties of the data. © 1997 OPA (Overseas Publishers Association) Amsterdam B. V. Published under license in The Netherlands under the Gordon and Breach Science Publishers imprint