Query result size estimation using a novel histogram-like technique: the rectangular attribute cardinality map

The Rectangular Attribute Cardinality Map (R-ACM) is a new histogram-like approximation strategy that aims to approximate the density of the underlying attribute values using the philosophies of numerical integration. Analytically, it is shown that for the R-ACM, the distribution of an attribute value within the sector is Binomially distributed. Theoretical results show that the R-ACM scheme is much more accurate than the traditional histograms for query result size estimation