The Application of Spatial Approximations to Spatial Query Processing: A Systematic Review of Literature

• Pedro G. K. Bertella Universidade Tecnológica Federal do Paraná (UTFPR)
• Yuri K. Lopes Universidade do Estado de Santa Catarina (UDESC)
• Rafael A. P. Oliveira Universidade Tecnológica Federal do Paraná (UTFPR)
• Anderson C. Carniel Universidade Federal de São Carlos (UFSCar) http://orcid.org/0000-0002-8297-9894

DOI: https://doi.org/10.5753/sbbd.2021.17880

Resumo

Spatial approximations simplify the geometric shape of complex spatial objects. Hence, they have been employed to alleviate the evaluation of costly computational geometric algorithms when processing spatial queries. For instance, spatial index structures employ them to organize spatial objects in tree structures (e.g., the R-tree). We report experiments considering two real datasets composed of ∼1.5 million regions and ∼2.7 million lines. The experiments confirm the performance benefits of spatial approximations and spatial index structures. However, we also identify that a second processing step is needed to deliver the final answer and often requires higher processing time than the step that uses index structures only. It leads to the interest in studying how spatial approximations can be efficiently used to improve both steps. This paper presents a systematic review on this topic. As a result, we provide an overview and comparison of existing approaches that propose, evaluate, or make use of spatial approximations to optimize the performance of spatial queries. Further, we characterize them and discuss some future trends.

Palavras-chave: spatial database, spatial query processing, spatial approximation, spatial information retrieval, window query

Referências

Bandi, N., Sun, C., Agrawal, D., and El Abbadi, A. (2007). Fast computation of spatial selections and joins using graphics hardware. Information Systems, 32(8):1073-1100.

Beckmann, N., Kriegel, H.-P., Schneider, R., and Seeger, B. (1990). The R*-tree: An efficient and robust access method for points and rectangles. In ACM SIGMOD Int. Conf. on Management of Data, pages 322–331.

Brinkhoff, T., Horn, H., Kriegel, H.-P., and Schneider, R. (1993). A storage and access architecture for efficient query processing in spatial database systems. In Int. Symp. on Spatial Databases, pages 357–376.

Brinkhoff, T., Kriegel, H. ., and Schneider, R. (1993). Comparison of approximations of complex objects used for approximation-based query processing in spatial database systems. In Int. Conf. on Data Engineering, pages 40–49.

Brinkhoff, T. and Kriegel, H.-P. (1994). Approximations for a multi-step processing of spatial joins. In IGIS ’94: Geographic Information Systems, pages 25–34.

Brinkhoff, T., Kriegel, H.-P., Schneider, R., and Seeger, B. (1994). Multi-step processing of spatial joins. In ACM SIGMOD Int. Conf. on Management of Data, pages 197–208.

Carniel, A. C. (2020). Spatial information retrieval in digital ecosystems: A comprehensive survey. In Int. Conf. on Management of Digital EcoSystems, pages 10–17.

Carniel, A. C., Ciferri, R. R., and Ciferri, C. D. A. (2020). FESTIval: A versatile framework for conducting experimental evaluations of spatial indices. MethodsX, 7:1–19.

Egenhofer, M. J. and Herring, J. R. (1994). Categorizing binary topological relations between regions, lines and points in geographic databases. In The 9-Intersection: Formalism and Its Use for Natural-Language Spatial Predicates.

Fevgas, A., Akritidis, L., Bozanis, P., and Manolopoulos, Y. (2019). Indexing in flash storage devices: a survey on challenges, current approaches, and future trends. The VLDB Journal, 29:273–311.

Gaede, V. and Gunther, O. (1998). Multidimensional access methods. ACM Computing Surveys, 30(2):170–231.

Guttman, A. (1984). R-trees: A dynamic index structure for spatial searching. In ACM SIGMOD Int. Conf. on Management of Data, pages 47–57.

Kothuri, R. K. and Ravada, S. (2001). Efficient processing of large spatial queries using interior approximations. In Int. Conf. on Advances in Spatial and Temporal Databases, pages 404–421.

Pandey, V., Kipf, A., Neumann, T., and Kemper, A. (2018). How good are modern spatial analytics systems? VLDB Endowment, 11(11):1661–1673.

Pandey, V., van Rene, A., Kipf, A., and Kemper, A. (2020). How good are modern spatial libraries? Data Science and Engineering, 6:192–208.

Papadias, D., Sellis, T., Theodoridis, Y., and Egenhofer, M. J. (1995). Topological relations in the world of minimum bounding rectangles: A study with R-trees. In ACM SIGMOD Int. Conf. on Management of Data, pages 92–103.

Schneider, M. and Behr, T. (2006). Topological relationships between complex spatial objects. ACM Transactions on Database Systems, 31(1):39–81.

Sidlauskas, D., Chester, S., Tzirita Zacharatou, E., and Ailamaki, A. (2018). Improving spatial data processing by clipping minimum bounding boxes. In Int. Conf. on Data Engineering, pages 425–436.

Su, W., Wei, H., Yeh, J., and Chen, W. (2017). An efficient approach based on polygon approximation to query spatial data on digital archiving system. In Int. Conf. on Applied System Innovation, pages 389–392.