Optimal histograms for hierarchical range queries (extended abstract)
Nick Koudas, S. Muthukrishnan, Divesh Srivastava · 2000
) Nick Koudas AT&T Labs--Research [email protected] S. Muthukrishnan AT&T Labs--Research [email protected] Divesh Srivastava AT&T Labs--Research [email protected] 1 Introduction 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. Histograms capture attribute value distribution statistics in a space-efficient fashion. They hav...