# US 2012/0084287 A1 · Estimation of unique database values

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0084287 A1
- Document ID: US20120084287A1
- Status: Published application
- Kind: A1
- Application number: 12/895,683
- Filed: 2010-09-30
- Published: 2012-04-05
- Earliest claimed: 2010-09-30
- Assignees: Hewlett-Packard Development Company, L.P.
- Inventors: Choudur Lakshminarayan; Ramakumar Kosuru
- Web page: https://patentgrep.com/patent/US20120084287A1

## CPC

- G06F 16/2462: {Approximate or statistical queries}
- G06F 16/24545: {Selectivity estimation or determination}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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;
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; and
determining a number of unique values in the database based on calculated binary Bloom filter values.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 1)

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

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 1)

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

### Claim 8

A system for estimating unique values in a database, comprising:
a database in communication with the information server and configured to store the information values received over a computing network;
a data loader configure load the information values from the computing network to the database to be stored;
a data partitioning module configured to partition the information values into intervals;
a Bloom filter module configured to compute an interval specific Bloom filter for the intervals;
a unique value calculation module 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 configured to estimate a number of unique values in the database based on calculated binary Bloom filter values.

### Claim 9 (depends on 8)

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.

### Claim 10 (depends on 8)

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.

### Claim 11 (depends on 8)

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.

### Claim 12 (depends on 11)

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.

### Claim 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;
determining whether the information value when subjected to a Bloom filter is a 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 a unique value.

### Claim 14 (depends on 13)

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

### Claim 15 (depends on 14)

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.
