Histograms are being used as non-parametric selectivity estimators for one-dimensional data. For highdimensional data it is common to either compute onedimensional histograms for each attribute or to compute a multi-dimensional equi-width histogram for a set of attributes. This either yields small low-quality or large highquality histograms.

In this paper we introduce HIRED (HIgh-dimensional histograms with dimensionality REDuction): small highquality histograms for multi-dimensional data. HIRED histograms are adaptive, and they are based on the shape error and directional splits. The shape error permits a precise control of the estimation error of the histogram and, together with directional splits, yields a memory complexity that does not depend on the number of uniform attributes in the dataset. We provide extensive experimental results with synthetic and real world datasets. The experiments confirm that our method is as precise as state-of-the-art techniques and uses orders of magnitude less memory.