Apparatus and method for calculating the selectivity of a range query for multidimensional data

摘要

An apparatus and method for calculating the selectivity of a range query for multidimensional data using a multidimensional histogram are provided. A data space may be partitioned into one or more sub-spaces based on a sum of skew values of the one or more sub-spaces, a space-partitioning tree may be generated for the data space, and a multidimensional histogram may be generated for the data space based on the space-partitioning tree. A range query for multidimensional data may be processed based on the multidimensional histogram.

主权项

1. 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.