Optimal and approximate computation of summary statistics for range aggregates
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Marin J. Strauss · 2001
Fast estimates for aggregate queries are useful in database query optimization, approximate query answering and online query processing. Hence, there has been a lot of focus on “selectivity estimation”, that is, computing summary statistics on the underlying data and using that to answer aggregate queries fast and to a reasonable approximation. We present two sets of results for range aggregate queries, which are amongst the most common queries.