Abstract
Spatial data in CAD/CAM and geographic information systems involve arbitrarily-shaped 2- and 3-dimensional geometries. Queries on such complex geometry data involve identification of data geometries that interact with a specified query geometry. Since geometry-geometry comparisons are expensive due to the large sizes of the data geometries, spatial engines avoid unnecessary comparisons by first comparing the MBRs and filtering out irrelevant geometries. If the query geometry is large compared to the data geometries, this filtering technique may not be effective in improving the performance. In this paper, we describe how to reduce geometry-geometry comparisons by first filtering using the interior approximations of geometries (in addition to and after comparing the exteriors, i.e., the MBRs). We implemented this technique as part of the R-tree indexes in Oracle Spatial and observed that the query performance improves by more than 50% (or a factor of 2) for most queries on real spatial datasets.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
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.
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.
S. Berchtold, D. A. Keim, and H. P. Kreigel. The X-tree: An index structure for high dimensional data. Proc of the Int. Conf. on Very Large Data Bases, 1996.
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.
T. Brinkhoff, H. P. Kriegel, and R. Schneider. Comparison of approximations of complex objects in spatial database systems. In Proc. Int. Conf. on Data Engineering, pages 40–49, 1993.
T. Brinkhoff, H. P. Kriegel, and B. Seeger. Efficient processing of spatial joins using R-trees. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 237–246, 1994.
M. J. Egenhofer. Reasoning aobout binary topological relations. In Symposium on Spatial Databases, pages 271–289, 1991.
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.
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.
V. Gaede and O. Gunther. Multidimensional access methods. ACM Computing Surveys, 30(2), 1998.
A. Guttman. R-trees: A dynamic index structure for spatial searching. Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 47–57, 1984.
G. Hjaltson and H. Samet. Ranking in spatial databases. In Symposium on Spatial Databases (SSD), 1995.
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.
King-Ip Lin, H. V. Jagdish, and C. Faloutsos. The TV-tree: An index structure for high-dimensional data. VLDB Journal, 3:517–542, 1994.
W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, and P. Yanker. The QBIC project: Querying images by content using color, texture and shape. In Proc. of the SPIE Conf. 1908 on Storage and Retrieval for Image and Video Databases, volume 1908, pages 173–187, February 1993.
K. V. Ravikanth, S. Ravada, J. Sharma, and J. Banerjee. Indexing medium-dimensionality data in oracle. In Proc. ACM SIGMOD Int. Conf. on Management of Data, 1999.
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.
H. Samet. The design and analysis of spatial data structures Addison-Wesley Publishing Co., 1989.
T. Sellis, N. Roussopoulos, and C. Faloutsos. The rγ+-tree: A dynamic index for multi-dimensional objects. Proc of the Int. Conf. on Very Large Data Bases, 13:507–518, 1988.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kothuri, R.K., Ravada, S. (2001). Efficient Processing of Large Spatial Queries Using Interior Approximations. In: Jensen, C.S., Schneider, M., Seeger, B., Tsotras, V.J. (eds) Advances in Spatial and Temporal Databases. SSTD 2001. Lecture Notes in Computer Science, vol 2121. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47724-1_21
Download citation
DOI: https://doi.org/10.1007/3-540-47724-1_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42301-0
Online ISBN: 978-3-540-47724-2
eBook Packages: Springer Book Archive