Resumo: The processing of large spatial databases is still a relevant challenge in computing. Currently, there are several technologies capable of capturing large volumes of spatial data quickly and efficiently. However, when processing and capturing spatial data are compared, it becomes clear that over time, the evolution of processing could not keep up with the evolution of technologies used to capture spatial data, so this difference fully delays the procedure. Known techniques with histograms have been used to reduce the computational resources and speed up the processing of spatial queries, especially multiway joins. This research created a hybrid histogram from the improvements of two known histograms: the Euler Histogram and the MinSkew Histogram. While the Euler Histogram focuses on solving the problem known as multiple counting, the MinSkew Histogram focuses on improving the accuracy of the estimates for non-uniform datasets. As these two problems contribute to the estimative imprecision, the hypothesis of the research was that a hybrid histogram, which implements the two techniques, would contribute to the reduction of estimation errors and, consequently, speed up the processing of queries. Thus, we designed a histogram named EulerSkew that combines these two features. This monograph describes the implementation of the method and the experimentation. We built a way of visualizing the histogram structure in QGis (software used for visualizing spatial databases). Then, we implemented a search algorithm to evaluate the accuracy of the selectivity through a comparative performance test between the proposed new method and the two baselines (MinSkew Histogram and Euler Histogram). The results showed that the EulerSkew histogram is more assertive in polygonal data datasets surpassing the assertiveness of MinSkew.

Palavras-chave: Histogram; Selectivity Estimation; Window Query.

Monografia completa. Copyright © 2022. Todos os direitos reservados.

Citação: João Marcelo Teodoro de Sousa. EulerSkew Histogram: A Hybrid method to Improve the Selectivity Estimation of Spatial Window Queries. Monografia. Bacharelado em Ciência da Computação. Universidade Federal de Jataí. Jataí, GO, Brasil. 2022. 48p.

Copiar citação no formato bibtex.