Bloom filter compaction
AssigneeGoogle Inc.
InventorDavid C. Oliver
Life of this patent
Estimating the term…
Abstract
Systems and methods for Bloom filter compaction are described herein. A method embodiment includes reading a data corpus, inserting a plurality of data items from the data corpus into a Bloom filter, determining a number of the data items inserted, calculating a desired filter size based on the number, and constructing a compact Bloom filter based on the desired filter size. Another method embodiment includes generating a second bit vector from a first bit vector associated with a first Bloom filter, generating an empty second Bloom filter of a size based on the first bit vector, dividing the first Bloom filter's bit vector into a plurality of slices, and setting the second Bloom filter's bits based on an evaluation of the corresponding bits in each slice of the first Bloom filter's bit vector.
Claims22
A computer implemented method for Bloom filter compaction comprising the following steps implemented with at least one processor:
- inserting a plurality of data items from a data corpus into a first Bloom filter represented by a first bit vector;
- determining a filter size based on a number of the data items inserted into the first Bloom filter;
- dividing the first bit vector representing the first Bloom filter into a plurality of slices based on the filter size and a size of the first Bloom filter;
- and
- generating a second Bloom filter represented by a second bit vector from the plurality of slices of the first Bloom filter, wherein the second Bloom filter is a compact representation of the first Bloom filter and one or more bits in the second bit vector are based on an evaluation of corresponding bits in each slice resolved from the first bit vector representing the first Bloom filter.
A processor-based system for Bloom filter compaction comprising:
- one or more processors;
- a Bloom filter populator configured to insert a plurality of data items from a data corpus into a first Bloom filter represented by a first bit vector;
- and
- a compact Bloom filter generator configured to:
- determine a filter size based on a number of the data items inserted into the first Bloom filter;
- divide the first bit vector representing the first Bloom filter into a plurality of slices based on the filter size and a size of the first Bloom filter;
- and
- generate a second Bloom filter represented by a second bit vector from the plurality of slices of the first Bloom filter, wherein the second Bloom filter is a compact representation of the first Bloom filter and one or more bits in the second bit vector are based on an evaluation of corresponding bits in each slice resolved from the first bit vector representing the first Bloom filter,
- wherein the Bloom filter populator and the compact Bloom filter generator are implemented on the one or more processors.
A computer-readable storage device having computer-executable instructions stored thereon, execution of which, by a computing device, causes the computing device to perform operations comprising:
- inserting a plurality of data items from a data corpus into a first Bloom filter represented by a first bit vector;
- determining a filter size based on a number of the data items inserted into the first Bloom filter;
- dividing the first bit vector representing the first Bloom filter into a plurality of slices based on the filter size and a size of the first Bloom filter;
- and
- generating a second Bloom filter represented by a second bit vector from the plurality of slices of the first Bloom filter, wherein the second Bloom filter is a compact representation of the first Bloom filter and one or more bits in the second bit vector are based on an evaluation of corresponding bits in each slice resolved from the first bit vector representing the first Bloom filter.
Dependencies are inferred from the claim text.