Patent ID: 8843525

Claim:
An apparatus for calculating the selectivity of a range query for multidimensional data, the apparatus comprising: a tree generator configured to partition a data space into one or more sub-spaces based on a sum of skew values of the one or more sub-spaces, and to generate a plurality of space-partitioning trees for the data space; a minimal cover acquirer configured to acquire a plurality of minimal covers from the plurality of space-partitioning trees, each of the plurality of minimal covers including one or more nodes of a corresponding space-partitioning tree, and to select one of the plurality of minimal covers; and a histogram generator configured to generate a histogram for the data space based on the selected minimal cover, wherein the skew value of each sub-space is defined as a multiplication of a size of a corresponding sub-space and a standard deviation of a number of data in the corresponding sub-space.