Estimation of unique database values

• US 8,549,004 B2
• Filed: 09/30/2010
• Issued: 10/01/2013
• Est. Priority Date: 09/30/2010
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Lakshminarayan, Choudur, Kosuru, Ramakumar
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): Ahluwalia, Navneet K
• Application Number:
  US12/895,683
• Publication Number:
  US 20120084287A1
• Time in Patent Office: 1,097 Days
• Field of Search: 707735-740
• US Class Current: 707/737
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

Estimation of unique values in a database can be performed where a data field having multiple information values is provided in the database. The data field can be partitioned into multiple intervals such that each interval includes a range of information values. An interval specific Bloom filter can be calculated for each of the multiple intervals. A binary Bloom filter value can be calculated for an information value within an interval specific Bloom filter. The binary Bloom filter value can represent whether the information value is unique. A number of unique values in the database can be determined based on calculated binary Bloom filter values.

Claims

1. A method for estimating unique values in a database, comprising:

providing a data field in the database, the data field comprising a plurality of information values;

partitioning the data field into a plurality of intervals, each interval comprising a range of information values from the plurality of information values;

computing an interval specific Bloom filter for each of the plurality of intervals using a processor;

applying a hash function on an information value in an interval;

evaluating whether a result of the hash function returns a value of zero;

calculating a binary Bloom filter value for an information value within an interval specific Bloom filter, wherein the binary Bloom filter value represents whether information values are unique;

constructing credible sets to determine how many samples to use to determine a number of unique values; and

determining the number of unique values in the database based on calculated binary Bloom filter values.

2. A method as in claim 1, further comprising storing the interval specific Bloom filter for each of the plurality of intervals.

3. A method as in claim 2, further comprising:

adding a second data field to the database;

partitioning the second data field into intervals;

loading a corresponding interval specific Bloom filter;

calculating a binary Bloom filter value for an information value within an interval associated with an interval specific Bloom filter from the second data field, wherein the binary Bloom filter value represents whether the information value is unique; and

determining a number of unique values in the database based on calculated binary Bloom filter values.

4. A method as in claim 1, further comprising generating a histogram based on the number of unique values.

5. A method as in claim 1, further comprising incrementally determining a number of unique values in the database when a second data field is added to the database.

6. A method as in claim 1, further comprising:

loading the data field into the database using a data loader performing a load process; and

estimating the number of unique values in the data field during the load process.

7. A method as in claim 1, further comprising calculating a false positive probability of whether the binary Bloom filter value is accurate.

16. A method as in claim 1, further comprising making a statistical inference according to a Bayesian probability approach.

17. A method as in claim 1, further comprising converting each application of the Bloom filter into a series of zeroes and ones, where “

1”

indicates that a unique value is observed and “

0”

indicates that an observed sample has already been detected.

18. A method as in claim 17, further comprising modeling outcomes as a binomial random variable.

19. A method as in claim 18, further comprising wherein a yielded posterior distribution is used to construct Bayesian credible sets.

20. A method as in claim 1, further comprising estimating parameters of a beta distribution using moments as inputs to a posterior distribution.

8. A system implemented at least in part in program code stored in a non-transitory machine-readable medium and executable by a computer to estimate unique values in a database, the system comprising:

a database in communication with the information server and configured to store the information values received over a computing network;

a data loader executed by the computer and configured to load the information values from the computing network to the database to be stored;

a data partitioning module executed by the computer and configured to partition the information values into intervals;

applying a hash function on an information value in an interval;

evaluating whether a result of the hash function returns a value of zero;

a Bloom filter module executed by the computer and configured to compute an interval specific Bloom filter for the intervals;

a unique value calculation module executed by the computer and configured to calculate a binary Bloom filter value for an information value within an interval specific Bloom filter, wherein the binary Bloom filter value represents whether the information value is unique; and

an estimation module executed by the computer and configured to estimate a number of unique values in the database based on calculated binary Bloom filter values, wherein the estimation module constructs credible sets to determine how many samples to use.

9. A system as in claim 8, further comprising a histogram module configured to generate a histogram based on the estimation of the number of unique values.

10. A system as in claim 8, wherein the estimation module further comprises an incrementation module configured to incrementally estimate a number of unique values in the database when additional data values are added to the database.

11. A system as in claim 8, further comprising a Bloom filter repository in communication with the information server and configured to store the interval specific Bloom filters.

12. A system as in claim 11, wherein the Bloom filter module is further configured to reuse a stored interval specific Bloom filter when additional data values are added to the intervals in the database.

13. A method for estimating unique values in a database, comprising:

storing a data field in the database, the data field comprising a plurality of information values;

partitioning the data field into a plurality of intervals, each interval comprising a range of information values from the plurality of information values;

applying a hash function on an information value in an interval;

evaluating whether a result of the hash function returns a value of zero;

constructing credible sets to determine how many samples to use to determine a unique value;

determining whether the information, value When subjected to a Bloom filter is the unique value based on the result of the hash function returning a value of one;

calculating a false positive probability of the information value being the unique value.

14. A method as in claim 13, further comprising determining the number of bits to include in the Bloom filter.

15. A method as in claim 14, further comprising increasing an available computing memory used by the Bloom filter to increase accuracy of the Bloom filter.