Cost models for join queries in spatial databases
- 1 January 1998
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 476-483
- https://doi.org/10.1109/icde.1998.655810
Abstract
The join query is one of the fundamental operations in database management systems (DBMSs). Modern DBMSs should be able to support non traditional data, including spatial objects, in an efficient manner. Towards this goal, spatial data structures can be adopted in order to support the execution of join queries on sets of multidimensional data. The paper introduces analytical models that estimate the cost (in terms of node or disk accesses) of join queries involving two multidimensional indexed data sets using R tree based structures. In addition, experimental results are presented, which show the accuracy of the analytical estimations when compared to actual runs on both synthetic and real data sets. It turns out that the relative error rarely exceeds 15% for all combinations, a fact that makes the proposed cost models useful tools for efficient spatial query optimization.Keywords
This publication has 21 references indexed in Scilit:
- Efficient computation of spatial joinsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The effect of buffering on the performance of R-treesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On the analysis of indexing schemesPublished by Association for Computing Machinery (ACM) ,1997
- Size separation spatial joinPublished by Association for Computing Machinery (ACM) ,1997
- Spatial hash-joinsACM SIGMOD Record, 1996
- Spatial joins using seeded treesPublished by Association for Computing Machinery (ACM) ,1994
- On packing R-treesPublished by Association for Computing Machinery (ACM) ,1993
- Join processing in relational databasesACM Computing Surveys, 1992
- Redundancy in spatial databasesPublished by Association for Computing Machinery (ACM) ,1989
- R-treesPublished by Association for Computing Machinery (ACM) ,1984