Equi-depth multidimensional histograms

Multi-dimensional queries commonly occur in databases dealing with geographical, image, and VLSI databases.A typical two dimensional query in a geographical database might involve finding all cities within certain latitudinal and longitudinal bounds.Several multi-dimensional index struc tures for point data have been proposed in the literature.KDB trees Robinson81 and and Grid files Nievergelt84 are among the more popular ones.However, there has been no work in designing multi-dimensional histograms to aid in the optimization process using these multi-dimensional index structures.In order for an optimizer to select an appropriate access path for a multi-dimensional query, fairly accurate selectivity estimates must be available to it.Selectivity esti mates are also useful in determining appropriate join methods that follow the selections.In this paper we present an algorithm for generating equi-depth, multi-dimensional histograms.One might expect that the cost of building a D-dimensional histogram would be at least D times the cost of sorting the relation on a single attribute.We show, in our algorithm, that the sorting cost of building a D-dimensional histogram is significantly less than the cost of sorting the relation D times.We present a main memory data structure for storing the histograms and discuss two schemes for estimating the number of tuples that will be "etrieved by a given query.Experimental results are presented that show the efficacy of our histograms.The usefulness of a sampling technique in generating histograms at a very low cost is also explored. Related WorkThe System R optimizer Selinger79 used simple statis tics, such as the minimum and maximum values in a given column, to estimate selectivity factors.Using such simple statistics will produce good selectivity estimates only if the attribute values are uniformly distributed.Since attribute values can have other distributions, it has become