Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/39940
Title: Global optimization of histograms
Authors: Jagadish, H.V.
Jin, H.
Ooi, B.C. 
Tan, K.-L. 
Issue Date: 2001
Source: Jagadish, H.V.,Jin, H.,Ooi, B.C.,Tan, K.-L. (2001). Global optimization of histograms. Proceedings of the ACM SIGMOD International Conference on Management of Data : 223-234. ScholarBank@NUS Repository.
Abstract: Histograms are frequently used to represent the distribution of data values in an attribute of a relation. Most previous work has focused on identifying the optimal histogram (given a limited number of buckets) for a single attribute independent of other attributes/histograms. In this paper, we propose the idea of global optimization of histograms, i.e., single-attribute histograms for a set of attributes are optimized collectively so as to minimize the overall error in using the histograms. The idea is to allocate more buckets to histograms whose attributes are more frequently used and/or distributions are highly skewed. While the accuracy of some histograms is penalized (being assigned fewer buckets), we expect the global error to be low compared to the traditional method (of allocating equal number of buckets to each histogram). We propose two algorithms to determine the histograms to construct for a collection of attributes. The first is based on dynamic programming, and the second is a greedy algori thm. We compare the overall error of these algorithms against the traditional method. Extensive experiments are conducted and the results confirm the benefits of global optimal histograms in reducing the overall error. The extent of improvement depends on the data and query distributions, ranging from no benefit when there is no significant differences in the data distributions to over a factor of 100 reduction in error in some cases we tried. The time to compute global optimal histogram using dynamic programming is much longer than the time to compute optimal histograms separately for each attribute, and the difference widens at a faster rate as the number of histograms increases. With the greedy algorithm, the time penalty is small, but the error reduction is somewhat less as well. We propose a third algorithm, called greedy algorithm with remedy, that has running time similar to the greedy algorithm, but produces results close to global optimum. In fact, in every experiment that we tried, this algorithm fo und the exact global optimum.
Source Title: Proceedings of the ACM SIGMOD International Conference on Management of Data
URI: http://scholarbank.nus.edu.sg/handle/10635/39940
ISSN: 07308078
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

56
checked on Dec 16, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.