[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/564691.564755acmconferencesArticle/Chapter ViewAbstractPublication PagesmodConference Proceedingsconference-collections
Article

Quadtree and R-tree indexes in oracle spatial: a comparison using GIS data

Published: 03 June 2002 Publication History

Abstract

Spatial indexing has been one of the active focus areas in recent database research. Several variants of Quadtree and R-tree indexes have been proposed in database literature. In this paper, we first describe briefly our implementation of Quadtree and R-tree index structures and related optimizations in Oracle Spatial. We then examine the relative merits of two structures as implemented in Oracle Spatial and compare their performance for different types of queries and other operations. Finally, we summarize experiences with these different structures in indexing large GIS datasets in Oracle Spatial.

References

[1]
W. M. Badaway and W. Aref. On local heuristics to speed up polygon-polygon intersection tests. In Proceedings of ACM GIS International Conference, pages 97-102, 1999.
[2]
N. Beckmann, H. Kriegel, R. Schneider, and B. Seeger. The R* tree: An efficient and robust access method for points and rectangles. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 322-331, 1990.
[3]
S. Berchtold, D. A. Keim, and H. P. Kreigel. The X-tree: An index structure for high dimensional data. Procof the Int. Conf. on Very Large Data Bases, 1996.
[4]
S. Berchtold, D. A. Keim, H.-P. Kriegel, and T. Seidl. A new technique for nearest neighbor search in high-dimensional space. IEEE Trans. on Knowledge and Data Engineering, 12(1):45-57, 2000.
[5]
T. Brinkhoff, H. Horn, H. P. Kriegel, and R. Schneider. A storage and access architecture for efficient query processing in spatial database systems. In Symposium on Large Spatial Databases (SSD'93), LNCS 692, 1993.
[6]
S. Defazio, A. Daoud, L. A. Smith, and J. Srinivasan. Integrating ir and rdbms using cooperative indexing. In Proc. of ACM SIGIR Conf. on Information Retrieval, pages 84-92, 1995.
[7]
M. J. Egenhofer. Reasoning aobout binary topological relations. In Symposium on Spatial Databases, pages 271-289, 1991.
[8]
M. J. Egenhofer, A. U. Frank, and J. P. Jackson. A topological data model for spatial databases. In Symposium on Spatial Databases (SSD), pages 271-289, 1989.
[9]
H. Ferhatosmanoglu, E. Tuncel, D. Agrawal, and A. E. Abbadi. Approximate nearest neighbor searching in multimedia databases. In Proc. Int. Conf. on Data Engineering, pages 503-511, 2001.
[10]
P. Fischer and K. U. Hoffgen. Computing a maximum axis-aligned rectangle in a convex polygon. In Information Processing Letters, 51, pages 189-194, 1994.
[11]
V. Gaede and O. Gunther. Multidimensional access methods. ACM Computing Surveys, 30(2), 1998.
[12]
Y. J. Garcia, S. T. Leutenegger, and M. A. Lopez. A greedy algorithm for bulk loading R-trees. In Proc. of ACM GIS, 1998.
[13]
A. Guttman. R-trees: A dynamic index structure for spatial searching. Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 47-57, 1984.
[14]
G. Hjaltson and H. Samet. Ranking in spatial databases. In Symposium on Spatial Databases (SSD), 1995.
[15]
N. Katayama and S. Satoh. The SR-tree: An index structure for high-dimensional nearest-neighbor queries. Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 369-380, May 1997.
[16]
M. Kornacker, C. Mohan, and J. Hellerstein. Concurrency and recovery in GiST. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 62-72, Tucson, Arizon, June 1997.
[17]
S. T. Leutenegger, M. A. Lopez, and J. M. Edgington. STR: A simple and efficient algorithm for R-tree packing. In Proc. Int. Conf. on Data Engineering, 1997.
[18]
K.-I. Lin, H. V. Jagdish, and C. Faloutsos. The TV-tree: An index structure for high-dimensional data. VLDB Journal, 3:517-542, 1994.
[19]
D. B. Lomet and B. Salzberg. The hB-tree: A multi-attribute indexing method with good guaranteed performance. Proc. ACM Symp. on Transactions of Database Systems, 15(4):625-658, December 1990.
[20]
B. C. Ooi, C. Yu, K. L. Tan, and H. V. Jagadish. Indexing the distance: an efficient method to knn processing. In Procof the Int. Conf. on Very Large Data Bases, 2001.
[21]
D. Papadis, T. Sellis, Y. Theodoridis, and M. Egenhofer. Topological relations in the world of minimum bounding rectangles: a study with r-trees. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 92-103, 1995.
[22]
K. V. Ravi Kanth, D. Agrawal, Amr El Abbadi, and Ambuj K. Singh. Dimensionality reduction for similarity searching in dynamic databases. In Proc. ACM SIGMOD Int. Conf. on Management of Data, 1998.
[23]
K. V. Ravi Kanth and Siva Ravada. Efficient processing of large spatial queries using interior approximations. In Symposium on Spatial and Temporal Databases (SSTD), 2001.
[24]
K. V. Ravi Kanth, Siva Ravada, J. Sharma, and J. Banerjee. Indexing medium-dimensionality data in oracle. In Proc. ACM SIGMOD Int. Conf. on Management of Data, 1999.
[25]
N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 71-79, May 1995.
[26]
H. Samet. Recent developments in linear quadtree-based geographic information systems. Image and Vision Computing, 5(3):187-197, Aug. 1987.
[27]
H. Samet. The design and analysis of spatial data structures. Addison-Wesley Publishing Co., 1989.
[28]
T. Sellis, N. Roussopoulos, and C. Faloutsos. The r+-tree: A dynamic index for multi-dimensional objects. Procof the Int. Conf. on Very Large Data Bases, 13:507-518, 1988.
[29]
Y. Theodoridis and T. K. Sellis. Optimization issues in r-tree construction. In Geographic Information Systems (IGIS), pages 270-273, 1994.
[30]
Y. Theodoridis and T. K. Sellis. A model for the prediction of r-tree performance. In Proc. ACM Symp. on Principles of Database Systems, 1996.
[31]
F. Wang. Relational-linear quadtree approach for two-dimensional spatial representation and manipulation. IEEE Trans. on Knowledge and Data Engineering, 3(1):118-122, Mar. 1991.
[32]
D. White and R. Jain. Algorithms and strategies for similarity retrieval. Proc. of the SPIE Conference, 1996.
[33]
D. White and R. Jain. Similarity indexing with the SS-tree. Proc. Int. Conf. on Data Engineering, pages 516-523, 1996.

Cited By

View all
  • (2024)Rapidash: Efficient Detection of Constraint ViolationsProceedings of the VLDB Endowment10.14778/3659437.365945417:8(2009-2021)Online publication date: 1-Apr-2024
  • (2024)A Unified Model for Spatio-Temporal Prediction Queries with Arbitrary Modifiable Areal Units2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00111(1352-1365)Online publication date: 13-May-2024
  • (2023)Improving NoSQL Spatial-Query Processing with Server-Side In-Memory R*-Tree Indexes for Spatial Vector DataSustainability10.3390/su1503244215:3(2442)Online publication date: 30-Jan-2023
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
SIGMOD '02: Proceedings of the 2002 ACM SIGMOD international conference on Management of data
June 2002
654 pages
ISBN:1581134975
DOI:10.1145/564691
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: 03 June 2002

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

SIGMOD/PODS02

Acceptance Rates

SIGMOD '02 Paper Acceptance Rate 42 of 240 submissions, 18%;
Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)57
  • Downloads (Last 6 weeks)6
Reflects downloads up to 14 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Rapidash: Efficient Detection of Constraint ViolationsProceedings of the VLDB Endowment10.14778/3659437.365945417:8(2009-2021)Online publication date: 1-Apr-2024
  • (2024)A Unified Model for Spatio-Temporal Prediction Queries with Arbitrary Modifiable Areal Units2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00111(1352-1365)Online publication date: 13-May-2024
  • (2023)Improving NoSQL Spatial-Query Processing with Server-Side In-Memory R*-Tree Indexes for Spatial Vector DataSustainability10.3390/su1503244215:3(2442)Online publication date: 30-Jan-2023
  • (2023)Onboard Data Management Approach Based on a Discrete Grid System for Multi-UAV Cooperative Image LocalizationIEEE Transactions on Geoscience and Remote Sensing10.1109/TGRS.2023.333292861(1-17)Online publication date: 2023
  • (2023)SGPAC: generalized scalable spatial GroupBy aggregations over complex polygonsGeoInformatica10.1007/s10707-023-00491-827:4(789-816)Online publication date: 21-Mar-2023
  • (2023)Continuous Group Nearest Neighbor Query over Sliding WindowAdvanced Data Mining and Applications10.1007/978-3-031-46677-9_16(225-236)Online publication date: 5-Nov-2023
  • (2022)A real-time mix-adjusted median property price index enabled by an efficient nearest neighbour approximation data structureJournal of Banking and Financial Technology10.1007/s42786-022-00043-y6:2(135-148)Online publication date: 24-Aug-2022
  • (2022)Group Trip Planning Queries on Road Networks Using Geo-Tagged Textual InformationAdvanced Data Mining and Applications10.1007/978-3-030-95405-5_18(243-257)Online publication date: 31-Jan-2022
  • (2021)QRB-tree Indexing: Optimized Spatial Index Expanding upon the QR-tree IndexISPRS International Journal of Geo-Information10.3390/ijgi1011072710:11(727)Online publication date: 27-Oct-2021
  • (2021)Efficient Semantic Enrichment Process for Spatiotemporal TrajectoriesWireless Communications and Mobile Computing10.1155/2021/44887812021(1-13)Online publication date: 12-Nov-2021
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media