Progressive approximate aggregate queries with a multi-resolution tree structure
- 1 May 2001
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 30 (2), 401-412
- https://doi.org/10.1145/375663.375718
Abstract
Answering aggregate queries like SUM, COUNT, MIN, MAX, AVG in an approximate manner is often desirable when the exact answer is not needed or too costly to compute. We present an algorithm for answering such queries in multi-dimensional databases, using selective traversal of a Multi-Resolution Aggregate (MRA) tree structure storing point data. Our approach provides 100% intervals of confidence on the value of the aggregate and works iteratively, coming up with improving quality answers, until some error requirement is satisfied or time constraint as reached. Using the same technique we can also answer aggregate queries exactly and our experiments indicate that even for exact answering the proposed data structure and algorithm are very fast.Keywords
This publication has 8 references indexed in Scilit:
- How to avoid building DataBlades(R) that know the value of everything and the cost of nothingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Approximating multi-dimensional aggregate range queries over real attributesPublished by Association for Computing Machinery (ACM) ,2000
- Approximate computation of multidimensional aggregates of sparse data using waveletsPublished by Association for Computing Machinery (ACM) ,1999
- Online aggregationPublished by Association for Computing Machinery (ACM) ,1997
- Nearest neighbor queriesPublished by Association for Computing Machinery (ACM) ,1995
- The Quadtree and Related Hierarchical Data StructuresACM Computing Surveys, 1984
- R-treesPublished by Association for Computing Machinery (ACM) ,1984
- The K-D-B-treePublished by Association for Computing Machinery (ACM) ,1981