Full Citation

Title: An Information Theoretic Histogram for Single Dimensional Selectivity Estimation

Citation Type: Conference Paper

Publication Year: 2005

ISBN:

ISSN:

DOI:

NSFID:

PMCID:

PMID:

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 accuracy ranking. We believe that the literature has not adequately characterized the performance of previous techniques.

Url: https://fada.birzeit.edu/handle/20.500.11889/2439

User Submitted?: No

Authors: Sayrafi, Bassem; Giannella, Chris

Conference Name: Proceedings of the 2005 ACM Symposium on Applied Computing (SAC)

Publisher Location: Santa Fe, New Mexico

Data Collections: IPUMS USA

Topics: Population Data Science

Countries: United States