Melhorando o processamento de consultas espaciais usando aproximações consertivas

Abstract

The use of spatial information is getting progressively more attention in many fields of applications. This information is represented as instances of the spatial data types point, line, or region. Spatial databases are responsible for storing this information while offering both its access and manipulation in an agile manner. Spatial data access in a spatial database is accomplished through spatial queries which, in general, use spatial approximations to reduce their execution time. Spatial approximations are simpler geometric representations of spatial objects. Therefore, spatial query processing is done using two steps: filter and refinement. In the filter step, the query criteria are verified on the approximations of the spatial objects, due to this, the positive result set is imperfect. This way, the refinement step is necessary, because it will validate the query criteria on the original spatial object which belongs to the result set of the filter step. Thus, the final query result is obtained. The filter step has a low processing cost by only performing validations on approximations, whereas the refinement step has a high processing cost, due to the complexity of the geometries of the spatial objects processed by it. As a way to accelerate the execution of spatial queries, this project proposes the development, utilization, and validation of intermediary steps of processing (between filter and refinement) which use distinct spatial approximations to reduce the number of spatial objects that need to be processed in the refinement step. Implementations were developed that perform the calculation of spatial approximations, topological predicate checks, file storage and allow these approximations to be used in intermediate steps through the integration with FESTIval. For validation, an experiment was made using spatial queries and different combinations of approximations, which resulted in a combination that has the best performance among those tested. The combination of the MBC and 4-corner approximations stood out for its great balance of build time and query time.