Dynamic Selectivity Estimation for Multidimensional Queries

We have developed an adaptive selectivity estimation scheme for multidimensional queries which, experiments indicate, performs better than previously formulated non-adaptive methods when the distribution of the data is not known. Our approach uses a technique based on dynamic quantized spaces, a dynamic data structure developed for motion analysis in the field of computer vision. The objective of this research is to overcome the disadvantages of previously formulated non-adaptive, static methods which are relatively inaccurate in a dynamic database environment when the distribution of the data is not uniform. We have shown via many experiments that our approach is more flexible and more accurate in the computation of selectivity factors than both the equi-width and equi-depth histogram methods when the database is large and undergoes frequent update activity following a non-uniform distribution.