Progressive approximate aggregate queries with a multi-resolution tree structure Iosif Lazaridis and Sharad Mehrotra   View Paper (PDF)   Return to Multi-dimensional Data 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 is 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. DiSC'02 © 2003 Association for Computing Machinery