Article

An information theoretic histogram for single dimensional selectivity estimation

Authors:

Chris Giannella,

Bassem SayrafiAuthors Info & Claims

SAC '05: Proceedings of the 2005 ACM symposium on Applied computing

Pages 676 - 677

https://doi.org/10.1145/1066677.1066831

Published: 13 March 2005 Publication History

Get Access

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 our histograms to have the overall best accuracy on the real datasets. We also observe that the accuracy ranking of all methods varies significantly across datasets. As such, we observe results not consistent with several conclusions drawn in past literature. Thus, we believe a gap exists in the past accuracy characterization.

References

[1]

loannidis Y. A History of Histograms. Proc. VLDB, 19--30, 2003.

Digital Library

Google Scholar

[2]

Poosala V., Ioannidis Y., Haas P., and Shekita E. Improved Histograms for Selectivity Estimation of Range Predicates. Proc. SIGMOD, 294--305, 1996.

Digital Library

Google Scholar

[3]

Giannella C. and Sayrafi B. An Information Theoretic Histogram for Single Dimensional Selectivity Estimation. Technical Report TR584, Indiana University, 2004.

Google Scholar

[4]

Zhang Q. and Lin X. On Linear-Spline Based Histograms. Lecture Notes in Computer Science 2419, 354--366, 2002.

Digital Library

Google Scholar

[5]

Jagadish H., Koudas N., Muthukrishnan S., Poosala V., Sevcik K., and Suel T. Optimal Histograms with Quality Guarantees. Proc. VLDB, 275--286, 1998.

Digital Library

Google Scholar

Cited By

View all

Alguliyev RAliguliyev RSukhostat L(2021)Parallel batch k-means for Big data clusteringComputers & Industrial Engineering10.1016/j.cie.2020.107023152(107023)Online publication date: Feb-2021
https://doi.org/10.1016/j.cie.2020.107023
Johnson PAbdelfattah E(2018)Applying Machine Learning Models to Identify Forest Cover2018 9th IEEE Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON)10.1109/UEMCON.2018.8796830(471-474)Online publication date: Nov-2018
https://doi.org/10.1109/UEMCON.2018.8796830

Index Terms

An information theoretic histogram for single dimensional selectivity estimation
1. Information systems
  1. Data management systems
    1. Database management system engines

Recommendations

Proactive and reactive multi-dimensional histogram maintenance for selectivity estimation

Many state-of-the-art selectivity estimation methods use query feedback to maintain histogram buckets, thereby using the limited memory efficiently. However, they are ''reactive'' in nature, that is, they update the histogram based on queries that have ...
Generic cumulative annular bucket histogram for spatial selectivity estimation of spatial database management system

Selectivity estimation is crucial to query optimizers in choosing an optimal execution plan in a given spatial query, and there has been a great deal of focus on how to achieve good selectivity estimation for finer spatial selection operators. Equally ...
The comparison between histogram method and index method in selectivity estimation
ICIC'11: Proceedings of the 7th international conference on Advanced Intelligent Computing Theories and Applications: with aspects of artificial intelligence

Today RDF data are proliferating so fast that RDF query engines are faced with very large graphs that contain thousand million of RDF triples. Often there are a lot of joins should be processed when using RDF query language-SPARQL execute queries and ...

Comments

Information & Contributors

Information

Published In

SAC '05: Proceedings of the 2005 ACM symposium on Applied computing

March 2005

1814 pages

ISBN:1581139640

DOI:10.1145/1066677

Conference Chair:
Hisham M. Haddad
Kennesaw State University
,
Editor:
Lorie M. Liebrock
New Mexico Institute of Mining and Technology, Socorro, NM
,
Program Chairs:
Andrea Omicini
Alma Mater Studiorum, Universita di Bologna, Italy
,
Roger L. Wainwright
Univerity of Tulsa, OK

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 March 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SAC05

Sponsor:

SIGAPP

SAC05: The 2005 ACM Symposium on Applied Computing

March 13 - 17, 2005

New Mexico, Santa Fe

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25

Sponsor:
sigapp

The 40th ACM/SIGAPP Symposium on Applied Computing

March 31 - April 4, 2025

Catania , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
300
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Alguliyev RAliguliyev RSukhostat L(2021)Parallel batch k-means for Big data clusteringComputers & Industrial Engineering10.1016/j.cie.2020.107023152(107023)Online publication date: Feb-2021
https://doi.org/10.1016/j.cie.2020.107023
Johnson PAbdelfattah E(2018)Applying Machine Learning Models to Identify Forest Cover2018 9th IEEE Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON)10.1109/UEMCON.2018.8796830(471-474)Online publication date: Nov-2018
https://doi.org/10.1109/UEMCON.2018.8796830

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Proactive and reactive multi-dimensional histogram maintenance for selectivity estimation

Generic cumulative annular bucket histogram for spatial selectivity estimation of spatial database management system

The comparison between histogram method and index method in selectivity estimation

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations