Improving Range Query Estimation on Histograms Francesco Buccafurri, Luigi Pontieri, Domenico Rosaci, and Domenico Saccà   View Paper (PDF)   Return to Session 16: Query Processing and Optimization-1 Abstract Histograms are used to summarize the contents of relations for the estimation of query result sizes into a number of buckets. Several techniques (e.g., MaxDiff and V-Optimal) have been proposed in the past for determining bucket boundaries which provide better estimations. This paper proposes to use 32 bit information (4-level tree index) for each bucket for storing approximated cumulative frequencies at 7 internal intervals of a bucket. Both theoretical analysis and experimental results show that the 4-level tree index provides the best frequency estimation inside a bucket. The index is later added to two well-known techniques for constructing histograms, MaxDiff and V-Optimal, thus obtaining high improvements in the frequency estimation over inter-bucket ranges w.r.t. the original methods. DiSC'03 © 2003 Association for Computing Machinery