Enhancing Histograms by Tree-Like Bucket Indices

Details Enhancing Histograms by Tree-Like Bucket Indices Enhancing Histograms by Tree-Like Bucket Indices

2005-01-11

arxiv.org/abs/cs/0501020v1

Computer Science

Data Structures and Algorithms

26 pages, 9 figures

Scientific paper

Histograms are used to summarize the contents of relations into a number of buckets for the estimation of query result sizes. Several techniques (e.g., MaxDiff and V-Optimal) have been proposed in the past for determining bucket boundaries which provide accurate estimations. However, while search strategies for optimal bucket boundaries are rather sophisticated, no much attention has been paid for estimating queries inside buckets and all of the above techniques adopt naive methods for such an estimation. This paper focuses on the problem of improving the estimation inside a bucket once its boundaries have been fixed. The proposed technique is based on the addition, to each bucket, of 32-bit additional information (organized into a 4-level tree index), storing approximate cumulative frequencies at 7 internal intervals of the bucket. Both theoretical analysis and experimental results show that, among a number of alternative ways to organize the additional information, the 4-level tree index provides the best frequency estimation inside a bucket. The index is later added to two well-known histograms, MaxDiff and V-Optimal, obtaining the non-obvious result that despite the spatial cost of 4LT which reduces the number of allowed buckets once the storage space has been fixed, the original methods are strongly improved in terms of accuracy.

Affiliated with

Also associated with

No associations

Rating

Enhancing Histograms by Tree-Like Bucket Indices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Enhancing Histograms by Tree-Like Bucket Indices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enhancing Histograms by Tree-Like Bucket Indices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-201640