Method for constructing a histogram

1. A method for constructing a histogram, comprising:

sampling attributes in a column of a database on a server;

determining a bucket set comprising a number of buckets that represents a distribution of the attributes with minimum error, wherein at least one bucket includes boundaries and an approximation of a count of attributes falling within the boundaries;

determining a precision for encoding the approximation, wherein a histogram having the bucket set fits within a storage limit and wherein the precision includes a bit threshold for the approximation of the count of the attributes; and

storing the histogram for the database by encoding the approximation with the precision for encoding the approximation.

2. The method of claim 1 , wherein determining the precision for encoding the approximation comprises:

computing a precision value and an error metric for a bucket set;

storing the precision value and the error metric in a table; and

retrieving the precision for encoding the approximation for use in storing the histogram.

3. The method of claim 2 , wherein the error metric is a sum squared error.

4. The method of claim 1 , wherein the approximation is a scalar representation of the count of attributes.

5. The method of claim 4 , wherein the precision for encoding the approximation is such that

(

B

-

1

)

⁢

log

2

⁢

⁢

k

+

B

⁢

⁢

log

2

⁢

⌈

(

n

Δ

+

1

)

⌉

is no greater than the storage limit, where Δ is a precision value, B is the number of buckets, (and where n attributes can take on any of k values) k is a number of possible values the attributes, n is the number of attributes.

6. The method of claim 1 , wherein the approximation is a vector representation of the count of attributes.

7. The method of claim 6 , wherein the approximation is a vector selected from a pre-defined set of vectors.

8. The method of claim 6 , wherein the approximation is a vector from a lattice {tilde over (Λ)} i that approximates a count vector with minimum error.

9. The method of claim 8 , wherein the precision for encoding the approximation is

min{α:( B− 1)log k+B log r (α, B )≦ R},

where r (α,B) is the number of points in the lattice that can approximate the count vector,

α is a scaling factor for lattice {tilde over (Λ)} i , B is the number of buckets, k is a number of possible values for the attributes, and R is the storage limit.

10. The method of claim 1 , wherein the attributes are created by converting text data into integers.

11. A non-transitory computer-readable storage medium having tangibly stored thereon computer-readable instructions for execution by a processor to perform a method of mapping a distribution of attributes in a database, comprising:

determining a bucket set comprising a number of buckets that represents the distribution with minimum error, wherein each bucket contains an approximation of a count of attributes;

determining a precision for which a histogram comprising the bucket set fits within a storage limit, wherein the precision includes a bit threshold for the approximation of the count of attributes; and

storing the histogram by encoding the approximation with the precision.

12. The non-transitory computer-readable storage medium of claim 11 , wherein determining the precision comprises computing a precision value and an error metric for a bucket set and

storing the precision value and the error metric in a table;

retrieving the precision for storing the histogram.

13. The non-transitory computer-readable storage medium of claim 12 , wherein the error metric is a sum squared error.

14. The non-transitory computer-readable storage medium of claim 11 , wherein the approximation is a scalar representation of the count of attributes.

15. The non-transitory computer-readable storage medium of claim 14 , wherein the precision is such that

(

B

-

1

)

⁢

log

2

⁢

⁢

k

+

B

⁢

⁢

log

2

⁢

⌈

(

n

Δ

+

1

)

⌉

is no greater than the storage limit, where Δ is a precision value, B is the number of buckets, (and where n attributes can take on any of k values) k is a number of possible values the attributes, and n is the number of attributes.

16. The non-transitory computer-readable storage medium of claim 11 , wherein the approximation is a vector representation of the count of attributes.

17. The non-transitory computer-readable storage medium of claim 16 , wherein the approximation is a vector selected from a pre-defined set of vectors.

18. The non-transitory computer-readable storage medium of claim 17 , wherein the approximation is a vector from a lattice {tilde over (Λ)} i that approximates a count vector with minimum error.

19. The non-transitory computer-readable storage medium of claim 18 , wherein the precision meets

min{α:( B− 1)log k+B log r (α, B )≦ R}

where r (α,B) is the number of points in the lattice that can approximate the count vector,

α is a scaling factor for lattice {tilde over (Λ)} i , B is the number of buckets, k is a number of possible values for the attributes, and R is the storage limit.

20. A system for processing data in a database, comprising:

a database that includes plurality of attributes arranged in a column;

a query processor to query the column;

a computer-readable storage medium having stored thereon computer-readable instructions for execution by the query processor to perform a method of mapping a distribution of attributes in a database, said method comprising:

determining a bucket set comprising a number of buckets that represents the distribution with minimum error, wherein each bucket contains an approximation of a count of attributes;

determining a precision for which a histogram comprising the bucket set fits within a storage limit, wherein the precision includes a bit threshold for the approximation of the count of attributes; and

storing the histogram by encoding the count approximation with the precision.