A quad-tree based multiresolution approach for two-dimensional summary data

Evaluating aggregate range queries by accessing a compressed representation of the data is a widely adopted solution to the problem of efficiently retrieving aggregate information from large amounts of data. Although several summarization techniques have been proposed which are effective in reducing the amount of time needed for computing aggregates, querying summary data often results in dramatically inaccurate estimates, due to the difficulty of limiting the loss of information resulting from data compression. Thus, a crucial issue regarding the definition of summarization techniques is to retain a reasonable degree of approximation in reconstructing query answers. Following the idea that an effective ad-hoc solution to this problem can be found in specific application domains, in this paper we restrict our attention to the case of two-dimensional data, which is relevant for a number of applications. Our proposal is a summarization technique where blocks of data resulting from a quad-tree based partition of the two-dimensional domain are summarized into aggregate values and possibly associated with indices, i.e., compact structures providing an approximate description the original data inside them. Several experimental results are presented showing that our technique results in data synopses providing query estimates having error rates lower than other techniques tailored at data with a generic dimensionality, such as wavelets and various types of multi-dimensional histogram.

► Quad-tree partitions as a basis for constructing histograms on two-dimensional data.
► Bit-wise encoding of the histogram for improving its accuracy.
► Two-dimensional indices exploiting numerical approximation for intra-bucket summarization.