More Web Proxy on the site http://driver.im/

Article

Free access

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

Authors:

Dimitris Papadias,

Yannis Theodoridis,

Max J. EgenhoferAuthors Info & Claims

SIGMOD '95: Proceedings of the 1995 ACM SIGMOD international conference on Management of data

Pages 92 - 103

https://doi.org/10.1145/223784.223798

Published: 22 May 1995 Publication History

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]

Allen, J.F. (1983) Maintaining Knowledge about Temporal Intervals. Communications of ACM, Vol 26(11), pp. 832- 843.

Digital Library

[2]

Beckmann, N., Kriegel, H.P. Schneider, R., Seeger, B. (1990) The R*-tree: an Efficient and Robust Access Method for Points and Rectangles. In the Proceedings of ACM- SIGMOD Conference.

Digital Library

[3]

Brinkhoff, T., Kriegel, H.P, Schneider, R. (1993) Comparison of Approximations of Complex Objects used for Approximation-based Query Processing in Spatial Database Systems. In the Proceedings of 9th International Conference on Data Engineering.

Digital Library

[4]

Brinkhoff, T., Kriegel, H.P., Schneider, R., Seeger, B. (1994) Multi-Step Processing of Spatial Joins. in the Proceedings of ACM-SIGMOD Conference.

Digital Library

[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]

Egenhofer, M. (1991) Reasoning about Binary Topological Relations. In the Proceedings of the Second Symposium on the Design and Implementation of Large Spatial Databases. Springer Verlag LNCS.

Digital Library

[7]

Egenhofer, M. (1993) Definition of Line-Line Relations for Geographic Databases. Data Engineering, Vol 16(6), pp. 40-45.

[8]

Egenhofer, M. (1994) Spatial SQL: A Query and Presentation Language. IEEE Transactions on Data and Knowledge Engineering, 6(1), 86-95.

Digital Library

[9]

Egenhofer, M., A1-Taha, K. (1992) Reasoning about Gradual Changes of Topological Relationships. In the Proceedings of the International Conference GIS - From Space to Territory: Theories and Methods of Spatio-Temporal Reasoning in Geographic Space. Springer Verlag LNCS.

Digital Library

[10]

Frank, A. U. (1995) Qualitative Spatial Reasoning: Cardinal Directions as an Example. To appear in the International Journal of Geographic Information Systems.

[11]

Freksa, C. (1992) Temporal Reasoning Based on Semi- Intervals. Artificial Intelligence Vol 54, pp. 199-227.

Digital Library

[12]

Glasgow, J.I., Papadias, D. (1992) Computational Imagery. Cognitive Science, Vol 16, pp. 355-394.

[13]

Greene, D. (1989) An Implementation and Performance Analysis of Spatial Data Access Methods. In the Proceedings of the 5th International Conference on Data Engineering.

Digital Library

[14]

Grigni M., Papadias, D., Papadimitriou, C. (1995) Topological Inference. Submitted.

[15]

Guttman, A. (1984) R-trees: a Dynamic Index Structure for Spatial Searching. In the Proceedings of ACM-SIGMOD Conference.

Digital Library

[16]

Hadzilacos, T., Tryfona, N. (1992) A Model for Expressing Topological Integrity Constraints in Geographic Databases. in the Proceedings of the International Conference GIS - From Space to Territory: Theories and Methods of Spatio-Temporal Reasoning in Geographic Space. Springer Verlag LNCS.

Digital Library

[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]

Papadias, D., Sellis, T. (1994) The Qualitative Representation of Spatial Knowledge in two-dimensional Space. VLDB Journal, Special Issue on Spatial Databases, Vol 3, pp. 479-516.

Digital Library

[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]

Papadias, D., Theodoridis, Y., Sellis, T. (1994) The Retrieval of Direction Relations Using R trees. In the Proceedings of the 5th Conference on Database and Expert Systems Applications. Springer Veflag LNCS.

Digital Library

[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]

Roussopoulos, N., Kelley, F., Vincent, F. (1995) Nearest Neighbor Queries. In the Proceedings of ACM-SIGMOD Conference.

Digital Library

[27]

Sellis, T., Roussopoulos, N., Faloutsos, C. (1987) The R+-tree: A Dynamic Index for Multi-Dimensional Objects. in the Proceedings of the 13th VLDB conference.

Digital Library

[28]

Sistla, P., Yu, C., Haddad, R. (1994) Reasoning about Spatial Relationships in Picture Retrieval Systems. In the Proceedings of the 20th VLDB Conference.

Digital Library

Cited By

Chaves Carniel A(2023)Defining and designing spatial queries: the role of spatial relationshipsGeo-spatial Information Science10.1080/10095020.2022.216392427:6(1868-1892)Online publication date: 17-May-2023
Fontenla-Carrera GFernández Vilán ÁIzquierdo Belmonte P(2023)Automatic Identification of Kinematic Diagrams with Computer VisionProceedings of the XV Ibero-American Congress of Mechanical Engineering10.1007/978-3-031-38563-6_62(425-431)Online publication date: 3-Aug-2023
(2023)Geospatial Data ScienceundefinedOnline publication date: 9-Jun-2023
Show More Cited By

Recommendations

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

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 ...
Relations between distance-based and degree-based topological indices

Let W, Sz, PI, and WP be, respectively, the Wiener, Szeged, PI, and Wiener polarity indices of a molecular graph G. Let M1 and M2 be the first and second Zagreb indices of G. We obtain relations between these classical distance- and degree-based ...
Spatial indexing by virtual bounding rectangles for high-dimensional data
Information organization and databases

This chapter presents a new indexing scheme, the Subspace Coding Method (SCM), that offers high performance similarity retrieval. Indices in the R-tree family generate tree structure using MBRs (Minimum bounding rectangles) or MBSs (Minimum bounding ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '95: Proceedings of the 1995 ACM SIGMOD international conference on Management of data

June 1995

508 pages

ISBN:0897917316

DOI:10.1145/223784

Editors:
Michael Carey
Univ. of Wisconsin
,
Donovan Schneider
Red Brick Systems

ACM SIGMOD Record Volume 24, Issue 2
May 1995
490 pages
ISSN:0163-5808
DOI:10.1145/568271
Issue’s Table of Contents

Copyright © 1995 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 May 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS95

Sponsor:

SIGMOD/PODS95: Joint ACM SIGMOD Intl Conference on Management of Data and ACM SIGACT-SIGMOD- SIGART Symposium on Principles of Database Systems

May 22 - 25, 1995

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

171
Total Citations
View Citations
1,198
Total Downloads

Downloads (Last 12 months)123
Downloads (Last 6 weeks)31

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chaves Carniel A(2023)Defining and designing spatial queries: the role of spatial relationshipsGeo-spatial Information Science10.1080/10095020.2022.216392427:6(1868-1892)Online publication date: 17-May-2023
Fontenla-Carrera GFernández Vilán ÁIzquierdo Belmonte P(2023)Automatic Identification of Kinematic Diagrams with Computer VisionProceedings of the XV Ibero-American Congress of Mechanical Engineering10.1007/978-3-031-38563-6_62(425-431)Online publication date: 3-Aug-2023
(2023)Geospatial Data ScienceundefinedOnline publication date: 9-Jun-2023
Koudas NLi RXarchakos I(2022)Video Monitoring QueriesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.304860634:10(5023-5036)Online publication date: 1-Oct-2022
Macedo RPaulo JPereira JBessani A(2020)A Survey and Classification of Software-Defined Storage SystemsACM Computing Surveys10.1145/338589653:3(1-38)Online publication date: 28-May-2020
Koudas NLi RXarchakos I(2020)Video Monitoring Queries2020 IEEE 36th International Conference on Data Engineering (ICDE)10.1109/ICDE48307.2020.00115(1285-1296)Online publication date: Apr-2020
Xarchakos IKoudas NBoncz PManegold SAilamaki ADeshpande AKraska T(2019)SVQProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3320230(2013-2016)Online publication date: 25-Jun-2019
Atluri GKarpatne AKumar V(2018)Spatio-Temporal Data MiningACM Computing Surveys10.1145/316160251:4(1-41)Online publication date: 22-Aug-2018
Bai LZhu LZhao Y(2018)Determining Topological Relations of Fuzzy Spatiotemporal Regions Over Time in XMLIEEE Access10.1109/ACCESS.2018.28785216(65620-65634)Online publication date: 2018
Uddin MStadler RClemm A(2018)A bottom‐up design for spatial search in large networks and cloudsInternational Journal of Network Management10.1002/nem.204128:6Online publication date: 8-Nov-2018
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents