Multi-dimensional selectivity estimation using compressed information

Abstract

For multimedia databases, the fuzzy query consists of a logical combination of content based similarity queries on features such as the color and the shape which are represented in continuous dimensions. Since the similarity query is intrinsically multi-dimensional, the multi-dimensional selectivity estimation is required in order to optimize a fuzzy query. For traditional databases, the query optimizer requires the multi-dimensional selectivity estimation for queries referencing multiple attributes from the same relation. The histogram is popularly used for the selectivity estimation. But the histogram has shortcomings as follows: First, it is difficult to estimate the selectivity of a similarity query using the histogram, since the typical similarity query has the shape of the hyper sphere and the range of features is continuous. Second, the histogram is efficient and practically the most preferable at a low dimensionality, particularly 1-dimension. However it suffers from the `dimensionality curses` at a high dimensionality, since the number of buckets is increased explosively. This causes severe problems of the high storage overhead and the high error rate at a high dimensionality. Third, most histograms do not support dynamic updates. This causes the periodical reconstruction of the histogram. With above motivations, we propose a novel approach for the multi-dimensional selectivity estimation of a query in continuous dimensions. Compressed information from a large number of small-sized buckets is maintained using the discrete cosine transform (DCT). This enables low error rates and low storage overheads even in a high dimensionality. Using the continuity property of the DCT we can make rectangles of any sizes in the data space in order to get approximate selectivity answers of queries of any shapes. In addition, this approach supports dynamic data updates, therefore it has the advantage of eliminating the overhead of periodical reconstructions of the compr...