Efficient algorithms for polygonal aggregation based on polygonal tessellation

This is an electronic version of the paper presented at the Jornadas de Ingeniería del Software y Bases de Datos, JISBD 2011, held in La Coruña on 2011In this paper, we examine the problem of efficiently computing aggregate functions over polygonal regions of space. We first formalize a class of effi- cient region-based aggregation model, where the aggregation query is computed by representing the query region with pre-defined regions using set operations. By focusing on a grid tessellation, we first generalize the aggregation problem from the case of query regions that are isothetic rectangles to polygons with isothetic edges, and show that the aggregation query can be answered linear in the number of vertices of the polygonal region. It is efficient since it is independent of the size of query region or the number of objects intersecting with the database. We further show how to produce approximate aggregations for query regions having the shape of arbitrary polygons, and support optimal block reads from the disk