Please use this identifier to cite or link to this item: http://hdl.handle.net/20.500.11889/2439
Title: An Information Theoretic Histogram for Single Dimensional Selectivity Estimation
Authors: Sayrafi, Bassem
Giannella, Chris
Issue Date: Mar-2005
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 previous techniques
Signal processing - Digital techniques
Description: Kassis,Mudar: Harb,Jihad:
URI: http://hdl.handle.net/20.500.11889/2439
Appears in Collections:Fulltext Publications

Files in This Item:
File Description SizeFormat 
6502.pdf181.43 kBAdobe PDFView/Open


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