Multi-dimensional selectivity estimation using compressed histogram information

This paper proposes a novel approach for the multi-dimensional selectivity estimation that enables low error rates and low storage overheads even in high dimensions, and has the advantage of supporting dynamic data updates by eliminating the overhead for periodical reconstructions of the compressed information.

Abstract

The database query optimizer requires the estimation of the query selectivity to find the most efficient access plan. For queries referencing multiple attributes from the same relation, we need a multi-dimensional selectivity estimation technique when the attributes are dependent each other because the selectivity is determined by the joint data distribution of the attributes. Additionally, for multimedia databases, there are intrinsic requirements for the multi-dimensional selectivity estimation because feature vectors are stored in multi-dimensional indexing trees. In the l-dimensional case, a histogram is practically the most preferable. In the multi-dimensional case, however, a histogram is not adequate because of high storage overhead and high error rates.