Please use this identifier to cite or link to this item:
|Title:||An Information Theoretic Histogram for Single Dimensional Selectivity Estimation|
|Publisher:||the Arab Reform Initaitive|
|Abstract:||We study the problem of one dimensional selectivity estimation in relational databases.
We introduce a new type of histogram based on information theory. We compare our histogram against
a large number of other techniques and on a wide array of datasets. We observe the entropy histograms
to fare well on real data. While they do not outperform all methods on all datasets, neither do any other
methods. The entropy histograms outperformed all other methods on 4 out of 9 real datasets and tied for
first on another two. This conclusion demonstrates that the entropy histograms are an excellent choice
of summary structure for selectivity estimation with respect to the state-of-the-art. We also observe
that all methods demonstrate a wide variety of behavior across real and synthetic datasets. Along these
lines we observe results not consistent with many conclusions drawn in the literature concerning method
Both authors were supported by NSF Grant IIS-0082407.
accuracy ranking. We believe that the literature has not adequately characterized the performance of
Signal processing - Digital techniques
|Appears in Collections:||Fulltext Publications|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.