page 1  (23 pages)
2to next section

Technical Report KDBSLAB-TR-94-06

Topological Relations in the World of Minimum Bounding Rectangles: a Study with R-trees

Dimitris Papadias
Department of Computer Science and Engineering
University of California, San Diego
La Jolla, California, USA 92093-0114
dimitris@cs.ucsd.edu

Yannis Theodoridis*
Department of Electrical and Computer Engineering
National Technical University of Athens
Zographou, Athens, GREECE 15773
theodor@theseas.ntua.gr

Timos Sellis*
Department of Electrical and Computer Engineering
National Technical University of Athens
Zographou, Athens, GREECE 15773
timos@theseas.ntua.gr

Max J. Egenhofer**
National Center for Geographic Information Analysis
University of Maine
Orono, Maine, USA 04469-5711
max@mecan1.maine.edu

Abstract Recent developments in spatial relations have led to their use in numerous
applications involving spatial databases. This paper is concerned with the retrieval of
topological relations in Minimum Bounding Rectangle-based data structures. We study the
topological information that Minimum Bounding Rectangles convey about the actual
objects they enclose, using the concept of projections. Then we apply the results in R-trees
and their variations, R+-trees and R*-trees in order to minimise disk accesses for queries
involving topological relations. We also investigate queries that involve complex spatial
conditions in the form of disjunctions and conjunctions and we discuss possible extensions.

1. INTRODUCTION

The representation and processing of spatial relations has recently gained much attention in Spatial Query Languages (Egenhofer, 1994, Papadias and Sellis, 1994b), Image and Multimedia Databases (Papadias et al., 1994a, Sistla et al., 1994), Geographic Applications (Frank, 1994), Spatial Reasoning (Glasgow, 1994) and Cognitive Science (Glasgow and Papadias, 1992). Several kinds of spatial relations have been defined and used. Egenhofer and Franzosa (1991), for instance, provided a mathematical framework for the definition of topological relations (e.g., inside, overlap), while Papadias and Sellis (1993) defined direction relations (e.g., north, north_east) using representative points. Kainz et al. (1993) modelled order relations

* Work partially supported by a research grant from the General Secretariat of Research and Technology of Greece (PENED 91).
** Work partially supported by the National Science Foundation under grant numbers IRI-9309230 and SBR-8810917 (for the National Center for Geographic Information and Analysis), Intergraph Corporation, Environmental Systems Research Institute, the Scientific Division of the North Atlantic Treaty Organization, and the Maine Mathematics and Science Alliance.