Optimal Histograms for Hierarchical Range Queries Nick Koudas, S. Muthukrishnan, and Divesh Srivastava   View Paper (PDF)   Return to Range Queries / Selectivity Estimation Abstract Now there is tremendous interest in data warehousing and OLAP applications. OLAP applications typically view data as having multiple logical dimensions (e.g., product, location) with natural hierarchies defined on each dimension, and analyze the behavior of various measure attributes (e.g., sales, volume) in terms of the dimensions. OLAP queries typically involve hierarchical selections on some of the dimensions (e.g., product is classified under the jeans product category, or location is in the north-east region), often aggregating measure attributes (see, e.g., [6]). Cost-based query optimization of such OLAP queries needs good estimates of the selectivity of hierarchical selections. References Note: References link to DBLP on the Web. [1] Ashraf Aboulnaga , Surajit Chaudhuri : Self-tuning Histograms: Building Histograms Without Looking at Data. SIGMOD Conference 1999 : 181-192 [2] Yannis E. Ioannidis : Universality of Serial Histograms. VLDB 1993 : 256-267 [3] Yannis E. Ioannidis , Stavros Christodoulakis : Optimal Histograms for Limiting Worst-Case Error Propagation in the Size of Join Results. TODS 18(4) : 709-748(1993) [4] Yannis E. Ioannidis , Viswanath Poosala : Balancing Histogram Optimality and Practicality for Query Result Size Estimation. SIGMOD Conference 1995 : 233-244 [5] H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Viswanath Poosala , Kenneth C. Sevcik , Torsten Suel : Optimal Histograms with Quality Guarantees. VLDB 1998 : 275-286 [6] H. V. Jagadish , Laks V. S. Lakshmanan , Divesh Srivastava : What can Hierarchies do for Data Warehouses? VLDB 1999 : 530-541 [7] Michael V. Mannino , Paicheng Chu , Thomas Sager : Statistical Profile Estimation in Database Systems. Computing Surveys 20(3) : 191-221(1988) [8] Yossi Matias , Jeffrey Scott Vitter , Min Wang : Wavelet-Based Histograms for Selectivity Estimation. SIGMOD Conference 1998 : 448-459 [9] M. Muralikrishna , David J. DeWitt : Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries. SIGMOD Conference 1988 : 28-36 [10] Viswanath Poosala , Yannis E. Ioannidis , Peter J. Haas , Eugene J. Shekita : Improved Histograms for Selectivity Estimation of Range Predicates. SIGMOD Conf. 1996 : 294-305 [11] Patricia G. Selinger , Morton M. Astrahan , Donald D. Chamberlin , Raymond A. Lorie , Thomas G. Price : Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979 : 23-34 BIBTEX @inproceedings{DBLP:conf/pods/KoudasMS00,   author    = {Nick Koudas and                 S. Muthukrishnan and                 Divesh Srivastava},    title     = {Optimal Histograms for Hierarchical Range Queries},    booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium                 on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,                 USA},    publisher = {ACM},    year      = {2000},    isbn      = {1-58113-214-X},    pages     = {196-204},    crossref  = {DBLP:conf/pods/00},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.