# US 2008/0307189 A1 · Data partitioning via bucketing bloom filters

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

- Number: US 2008/0307189 A1
- Document ID: US20080307189A1
- Status: Published application
- Kind: A1
- Application number: 11/811,619
- Filed: 2007-06-11
- Published: 2008-12-11
- Earliest claimed: 2007-06-11
- Assignees: Microsoft Corporation
- Inventors: Anton Mityagin; Kumar Chellapilla; Denis Charles
- Web page: https://patentgrep.com/patent/US20080307189A1

## CPC

- G06F 16/93: Document management systems
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Multiple Bloom filters are generated to partition data between first and second disjoint data sets of elements. Each element in the first data set is assigned to a bucket of a first set of buckets, and each element in the second data set is assigned to a bucket of a second set of buckets. A Bloom filter is generated for each bucket of the first set of buckets. The Bloom filter generated for a bucket indicates that each element assigned to that bucket is part of the first data set, and that each element assigned to a corresponding bucket of the second set of buckets is not part of the first data set. Additionally, a Bloom filter corresponding to a subsequently received element can be determined and used to identify whether that subsequently received element is part of the first data set or the second data set.

## Claims

### Claim 1

One or more computer storage media having stored thereon instructions that, when executed by one or more processors of a computing device, cause the one or more processors to:
identify a first data set of elements and a second data set of elements, wherein the first data set and the second data set are disjoint;
assign each element in the first data set to a bucket of a first set of buckets;
assign each element in the second data set to a bucket of a second set of buckets; and
generate, for each bucket of the first set of buckets, a Bloom filter that indicates that each element assigned to the bucket of the first set of buckets is part of the first data set, and that indicates that each element assigned to a corresponding bucket of the second set of buckets is not part of the first data set.

### Claim 2 (depends on 1)

One or more computer storage media as recited in claim 1, wherein:
to assign each element in the first data set to the bucket of the first set of buckets is to, for each element in the first data set:
generate a hash value for the element by applying a hash function to the element; and
assign the element to one bucket of the first set of multiple buckets that corresponds to the hash value for the element; and
to assign each element in the second data set to the bucket of the second set of buckets is to, for each element in the second data set:
generate a hash value for the element by applying the hash function to the element; and
assign the element to one bucket of the second set of multiple buckets that corresponds to the hash value for the element.

### Claim 3 (depends on 2)

One or more computer storage media as recited in claim 2, each bucket in the first set of multiple buckets having one corresponding bucket in the second set of multiple buckets, with corresponding buckets being identified by a same index value.

### Claim 4 (depends on 2)

One or more computer storage media as recited in claim 2, wherein to assign each element in the first data set to the bucket of the-first set of buckets is further to, for each element in the first data set, store a portion of the hash value for the element in a data structure representing the one bucket.

### Claim 5 (depends on 1)

One or more computer storage media as recited in claim 1, wherein to generate the Bloom filter for a first bucket of the first set of buckets is to:
generate a temporary Bloom filter for the first bucket;
for each of one or more elements in a second bucket of the second set of buckets, the first bucket corresponding to the second bucket, check whether the temporary Bloom filter returns a positive result for the element, the positive result indicating that the element was memorized by the temporary Bloom filter;
if the temporary Bloom filter returns the positive result for none of the elements of the second bucket, then use the temporary Bloom filter as the Bloom filter for the first bucket; and
if the temporary Bloom filter returns the positive result for at least one of the elements of the second bucket, then repeatedly generate new temporary Bloom filters until a temporary Bloom filter that returns the positive result for none of the elements of the second bucket is generated.

### Claim 6 (depends on 5)

One or more computer storage media as recited in claim 5, wherein to generate the new temporary Bloom filters is to use a new seed value for a set of hash functions used to create the new temporary Bloom filters.

### Claim 7 (depends on 1)

One or more computer storage media as recited in claim 1, wherein to assign each element in the first data set to the bucket of the first set of buckets is to, for each element in the first data set, store a hash value generated by applying a hash function to the element in a data structure representing the bucket to which the element is assigned.

### Claim 8 (depends on 1)

One or more computer storage media as recited in claim 1, wherein to assign each element in the first data set to the bucket of the first set of buckets is to, for each element in the first data set, store the element in a data structure representing the bucket to which the element is assigned.

### Claim 9 (depends on 1)

One or more computer storage media as recited in claim 1, wherein the instructions further cause the one or more processors to partition data among three or more data sets by repeating the identification, both of the assignments, and the generation recursively with additional data subsets of one or both of the first data set and the second data set.

### Claim 10 (depends on 1)

One or more computer storage media as recited in claim 1, wherein the instructions further cause the one or more processors to:
obtain data that is an element of either the first data set of elements or the second data set of elements;
determine a single Bloom filter that corresponds to the element, the single Bloom filter being one of multiple Bloom filters associated with the first data set, each of the multiple Bloom filters corresponding to different elements of the first data set; and
use the single Bloom filter to determine whether the element is part of the first data set of elements or the second data set of elements.

### Claim 11

A method of creating a set of Bloom filters to partition data into two disjoint data sets, the method comprising:
assigning elements of each of the two disjoint data sets to a bucket of a corresponding set of buckets; and
generating the set of Bloom filters, each Bloom filter corresponding to one bucket corresponding to a first data set of the two disjoint data sets, each Bloom filter indicating that each element in the first data set is part of the first data set, and further indicating that each element in a second data set of the two data sets is not part of the first data set.

### Claim 12 (depends on 11)

A method as recited in claim 11, wherein assigning elements of each of the, two disjoint data sets to a bucket of a corresponding set of buckets comprises:
for each element in the first data set:
generating a hash value for the element by applying a hash function to the element; and
assigning the element to one bucket of a first set of buckets corresponding to the first data set, the one bucket corresponding to the hash value for the element; and
for each element in the second data set:
generating a hash value for the element by applying the hash function to the element; and
assigning the element to one bucket of a second set of buckets corresponding to the second data set, the one bucket corresponding to the hash value for the element.

### Claim 13 (depends on 12)

A method as recited in claim 12, further comprising for each element in the first data set, storing a portion of the hash value for the element in a data structure representing the one bucket of the first set of buckets.

### Claim 14 (depends on 11)

A method as recited in claim 11, the generating comprising, for a first bucket in the set of buckets corresponding to the first data set:
generating a temporary Bloom filter for the first bucket;
for each of one or more elements in a second bucket of the set of buckets corresponding to the second data set, the first bucket corresponding to the second bucket, checking whether the temporary Bloom filter returns a positive result for the element, the positive result indicating that the element was memorized by the temporary Bloom filter;
if the temporary Bloom filter returns the positive result for none of the elements of the second bucket, then using the temporary Bloom filter as the Bloom filter for the first bucket; and
if the temporary Bloom filter returns the positive result for at least one of the elements of the second bucket, then repeatedly generating new temporary Bloom filters until a temporary Bloom filter that returns the positive result for none of the elements of the second bucket is generated.

### Claim 15 (depends on 14)

A method as recited in claim 14, wherein generating the new temporary Bloom filters comprises using a new seed value for a set of hash functions used to create the new temporary Bloom filters.

### Claim 16 (depends on 11)

A method as recited in claim 11, wherein assigning elements of the first data set to a bucket of a corresponding set of buckets comprises, for each element in the first data set, storing a hash value generated by applying a hash function to the element in a data structure representing the bucket to which the element is assigned.

### Claim 17 (depends on 11)

A method as recited in claim 11, wherein assigning elements of the first data set to a bucket of a corresponding set of buckets comprises, for each element in the first data set, storing the element in a data structure representing the bucket to which the element is assigned.

### Claim 18

One or more computer storage media having stored thereon instructions that, when executed by one or more processors of a computing device, cause the one or more processors to:
obtain data that is an element of either a first data set of elements or a second data set of elements, wherein the first data set and the second data set are disjoint;
determine a single Bloom filter that corresponds to the element, the single Bloom filter being one of multiple Bloom filters associated with the first data set, each of the multiple Bloom filters corresponding to different elements of the first data set; and
use the single Bloom filter to determine whether the element is part of the first data set of elements or the second data set of elements.

### Claim 19 (depends on 18)

One or more computer storage media as recited in claim 18, wherein to determine the single Bloom filter that corresponds to the element is to:
generate a hash value for the element using a hash function; and
identify as the single Bloom filter a Bloom filter of the multiple Bloom filters that has an index value that is the same as the hash value.

### Claim 20 (depends on 19)

One or more computer storage media as recited in claim 19, wherein the hash function is a same hash function as was previously used to assign elements of the first data set to a first set of buckets associated with the multiple Bloom filters during creation of the multiple Bloom filters.
