Abstract: Spatial join queries are essential to spatial data processing and also very compute-resource intensive, particularly when considering multiway spatial joins, which have many distinct ways of computing called execution plans. A poorly chosen plan increases the processing time and usage of computational resources and, consequently, we demand very effective methods for estimating the cost of queries such as spatial histograms. Recently studies identified that the type of spatial object in datasets (whether of line or polygon type) plays a significant role in the assertiveness of grid histogram-based estimation. However, estimation formulae in more sophisticated and recently proposed histograms, such as the Euler Histogram, did not receive this particular treatment. This work proposes a novel Euler Intermediate Histogram to estimate the cardinality of multiway spatial join queries, adapt the formulae of estimation to employ the type of objects in estimates, and consider datasets whose spatial extension does not align. We believe this is a more realistic scenario towards applying the methods to a spatial database. Our evaluation shows that the proposed model assertively compute cardinalities of spatial join queries and that the estimate based on the dataset object types significantly improves the assertiveness for Euler Histograms.

Keywords: Dados Espaciais; Multijunção Espacial; Histograma de Euler; Estimativa de Custo.

Complete monograph. Copyright © 2019. All rights reserved.

Disclaimer: Although the student carefully wrote the original abstract, and it was revised and improved, English is not him or the advisor' mother language. The original work is written in Portuguese.

Citation: Murilo Cunha dos Santos. Estimativa de Custo de Multijunções Espaciais usando Histogramas Intermediários de Euler para Datasets de Linhas e Polígonos. Monografia. Bacharelado em Ciências da Computação. Universidade Federal de Goiás, Regional Jataí. Jataí, GO, Brasil. 2019. 61p.

Copy citation in bibtex format.