US 7,743,013 B2Granted

Data partitioning via bucketing bloom filters

AssigneeMicrosoft Corporation

InventorsAnton Mityagin, Kumar Chellapilla, Denis Charles

Life of this patent

Estimating the term…

Loading patent…

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.

Claims17

Dependent claims

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

11 more elements

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

10 more elements

Dependencies are inferred from the claim text.