Topological relations in the world of minimum bounding rectangles: a study with R-trees

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 to 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.

REFERENCES

• 1: James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 [doi>10.1145/182.358434]
• 2: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 3: Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider, Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems, Proceedings of the Ninth International Conference on Data Engineering, p.40-49, April 19-23, 1993
• 4: Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, Multi-step processing of spatial joins, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.197-208, May 24-27, 1994, Minneapolis, Minnesota, United States
• 5: Clementini, E., Sharma, J., Egenhofer, M. (1995) Modeling Topological Spatial Relations: Strategies for Query Processing. To appear in the International Journal of Computer and Graphics.
• 6: Max J. Egenhofer, Reasoning about Binary Topological Relations, Proceedings of the Second International Symposium on Advances in Spatial Databases, p.143-160, August 28-30, 1991
• 7: Egenhofer, M. (1993) Definition of Line-Line Relations for Geographic Databases. Data Engineering, Vol 16(6), pp. 40-45.
• 8: M. J. Egenhofer, Spatial SQL: A Query and Presentation Language, IEEE Transactions on Knowledge and Data Engineering, v.6 n.1, p.86-95, February 1994 [doi>10.1109/69.273029]
• 9: Max J. Egenhofer , Khaled K. Al-Taha, Reasoning about Gradual Changes of Topological Relationships, Proceedings of the International Conference GIS - From Space to Territory: Theories and Methods of Spatio-Temporal Reasoning on Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, p.196-219, September 21-23, 1992
• 10: Frank, A. U. (1995) Qualitative Spatial Reasoning: Cardinal Directions as an Example. To appear in the International Journal of Geographic Information Systems.
• 11: Christian Freksa, Temporal reasoning based on semi-intervals, Artificial Intelligence, v.54 n.1-2, p.199-227, March 1992 [doi>10.1016/0004-3702(92)90090-K]
• 12: Glasgow, J.I., Papadias, D. (1992) Computational Imagery. Cognitive Science, Vol 16, pp. 355-394.
• 13: Diane Greene, An Implementation and Performance Analysis of Spatial Data Access Methods, Proceedings of the Fifth International Conference on Data Engineering, p.606-615, February 06-10, 1989
• 14: Grigni M., Papadias, D., Papadimitriou, C. (1995) Topological Inference. Submitted.
• 15: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 16: Thanasis Hadzilacos , Nectaria Tryfona, A Model for Expressing topological Integrity Constraints in Geographic Databases, Proceedings of the International Conference GIS - From Space to Territory: Theories and Methods of Spatio-Temporal Reasoning on Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, p.252-268, September 21-23, 1992
• 17: Keighan, E. (1993) Managing Spatial Data within the Framework of the Relational Model. Technical Report, Oracle Corporation, Canada.
• 18: Mark, D., Egenhofer, M. (1994) Calibrating the Meaning of Spatial Predicates from Natural Language: Line Region Relations. In the Proceedings of the 6th International Symposium on Spatial Data Handling. Taylor Francis.
• 19: Mark, D., Xia, F. (1994) Determining Spatial Relations between Lines and Regions in Arc/Info using the 9- Intersection Model. In ESRI User Conference.
• 20: MGE (1993) MGE Analyst Reference Manual. Intergraph Corporation.
• 21: Dimitris Papadias , Timos Sellis, Qualitative representation of spatial knowledge in two-dimensional space, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
• 22: Papadias, D., Theodoridis, Y. (1994) Spatial Relations, Minimum Bounding Rectangles and Spatial Data Structures. Technical Report, KDBSLAB-TR-94-06, National Technical University of Athens, Greece.
• 23: Dimitris Papadias , Yannis Theodoridis , Timos K. Sellis, The Retrieval of Direction Relations using R-trees, Proceedings of the 5th International Conference on Database and Expert Systems Applications, p.173-182, September 07-09, 1994
• 24: Papadias, D., Sellis, T. (1995) A Pictorial Query-By-Example Language. To appear in the Journal of Visual Languages and Computing, Special Issue on Visual Query Systems, March 95.
• 25: Randell, D. A., Cui, Z., Cohn., A., (1992) A Spatial Logic Based on Regions and Connection. in the Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning. Morgan Kaufmann.
• 26: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 27: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 28: A. Prasad Sistla , Clement T. Yu , R. Haddad, Reasoning About Spatial Relationships in Picture Retrieval Systems, Proceedings of the 20th International Conference on Very Large Data Bases, p.570-581, September 12-15, 1994

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Earth and atmospheric sciences

General Terms:
Algorithms, Design, Languages, Performance