Abstract: The processing of spatial queries has a notably high computing cost, especially considering multiway spatial joins where the query may be executed in different ways called execution plans. We usually use spatial histograms to select the best plan based on the number of objects returned by each query. One relevant type of histogram, due to its high precision, is the Annular Bucket Histogram or AB. However, the experiments made by the authors that proposed the technique didn’t contain comparisons with other methods using datasets with objects of different types and histograms of distinct grid sizes. This research shows a comparative analysis of the AB Histogram with other techniques proposed in the field: the MP histogram, the Euler histogram, and IHWAF. Our experiments demonstrated that the AB Histogram is more precise compared to the other methods. However, its large number of buckets resulted in a significantly longer build and query time. Also, we verified that datasets with polygonal data have poor use of the buckets when objects are side by side.

Keywords: Histogram; Selectivity Estimation; Window Query.

Complete monograph. Copyright © 2022. 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: Gabriel Portela Macedo Souza. Comparative Analysis of the AB Histogram for Window Queries in Line and Polygon Spatial Datasets. Monografia. Bacharelado em Ciência da Computação. Universidade Federal de Jataí. Jataí, GO, Brasil. 2022. 51p.

Copy citation in bibtex format.