A quad-tree based multiresolution approach for two-dimensional summary data
- 1 January 2003
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 36 (7), 127-137
- https://doi.org/10.1109/ssdm.2003.1214974
Abstract
In many application contexts, like statistical databases, scientific databases, query optimizers, OLAP, and so on, data are often summarized into synopses of aggregate values. Summarization has the great advantage of saving space, but querying aggregate data rather than the original ones introduces estimation errors which cannot be in general avoided, as summarization is a lossy compression. A central problem in designing summarization techniques is to retain a certain degree of accuracy in reconstructing query answers. In this paper we restrict our attention to two-dimensional data, which are relevant for a number of applications, and propose a hierarchical summarization technique, which is combined with the use of indices, i.e. compact structures providing an approximate description of portions of the original data. Experimental results show that the technique gives approximation errors much smaller than other "general purpose" techniques, such as wavelets and various types of multi-dimensional histogram.Keywords
This publication has 9 references indexed in Scilit:
- Improving range query estimation on histogramsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Wavelet synopses with error guaranteesPublished by Association for Computing Machinery (ACM) ,2002
- Selectivity Estimation of Complex Spatial QueriesLecture Notes in Computer Science, 2001
- Global optimization of histogramsPublished by Association for Computing Machinery (ACM) ,2001
- Progressive approximate aggregate queries with a multi-resolution tree structureACM SIGMOD Record, 2001
- Approximate computation of multidimensional aggregates of sparse data using waveletsPublished by Association for Computing Machinery (ACM) ,1999
- Data cube approximation and histograms via waveletsPublished by Association for Computing Machinery (ACM) ,1998
- Direction relations and two-dimensional range queries: optimisation techniquesData & Knowledge Engineering, 1998
- Wavelet-based histograms for selectivity estimationPublished by Association for Computing Machinery (ACM) ,1998