# US 10,503,737 B1 · Bloom filter partitioning > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,503,737 B1 - Document ID: US10503737B1 - Status: Granted - Kind: B1 - Application number: 14/675,476 - Filed: 2015-03-31 - Granted: 2019-12-10 - Earliest claimed: 2015-03-31 - Assignees: Maginatics LLC - Applicants: Maginatics LLC - Inventors: Thomas Manville; Julio Lopez; Shrinand Javadekar - Web page: https://patentgrep.com/patent/US10503737B1 ## CPC - G06F 16/2455: Query execution - G06F 16/24554: {Unary operations; Data partitioning operations} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A partitioned Bloom filter is disclosed. In various embodiments, a representation of an item is received. The representation is used to determine a partition with which the item is associated. A partition-specific Bloom filter is used to determine at least in part whether the item may be an element of a set with which the partition is associated. ## Claims ### Claim 1 A method, comprising: receiving, by one or more processors, a representation of an item; using, by one or more processors, the representation to determine a particular partition with which the item is associated, wherein the particular partition with which the item is associated is one of a plurality of partitions corresponding to a volume that comprises the item, and each of the plurality of partitions have a corresponding partition-specific Bloom filter; determining, by one or more processors, whether the item is an element of a set with which the particular partition is associated, wherein the set comprises one or more objects stored in a distributed file system, and wherein the determining of whether the item is an element in the set comprises: checking a partition-specific Bloom filter corresponding to the particular partition to determine if the item is an element of the set; in response to determining that the partition-specific Bloom filter indicates that the item is not an element of the set, determining that the item is not an element of the set; and in response to determining that the partition-specific Bloom filter indicates that the item is an element of the set, querying a table associated with the set for the representation of the item, and determining that the item is an element of the set in the event that the querying of the table associated with the set indicates that the set includes the item; dynamically determining to partition or resize the partition-specific Bloom filter based at least in part on a computed probability of the partition-specific Bloom filter rendering a false positive, the computed probability being based at least in part on one or more of a filter size and a number of elements in the particular partition corresponding to the partition-specific Bloom filter; and in response to determining to partition or resize the partition specific Bloom filter, partitioning or resizing the partition-specific Bloom filter independent of one or more other partition-specific Bloom filters corresponding to one or more other partitions of the plurality of partitions. ### Claim 2 (depends on 1) The method of claim 1, wherein the Bloom filter comprises a counting Bloom filter. ### Claim 3 (depends on 1) The method of claim 1, wherein the particular partition comprises a subset of the set. ### Claim 4 (depends on 1) The method of claim 1, wherein the representation comprises a hash. ### Claim 5 (depends on 1) The method of claim 1, wherein item comprises a chunk included in a set of one or more chunks into which a file has been segmented. ### Claim 6 (depends on 1) The method of claim 1, wherein the item comprises a chunk of data and representation comprises a hash of the chunk of data. ### Claim 7 (depends on 1) The method of claim 1, further comprising determining a number of partitions to associate with the set. ### Claim 8 (depends on 7) The method of claim 7, further comprising determining for one or more of the plurality of partitions an initial size of a corresponding partition-specific Bloom filter. ### Claim 9 (depends on 1) The method of claim 1, further comprising determining that the partition-specific Bloom filter is to be resized. ### Claim 10 (depends on 9) The method of claim 9, wherein the particular partition comprises a first partition; and further comprising resizing the partition-specific Bloom filter associated with the first partition without affecting operation of one or more other partition-specific Bloom filters associated the one or more other partitions of the plurality of partitions. ### Claim 11 (depends on 1) The method of claim 1, further comprising determining to rebuild the particular partition based at least in part on a count reflecting a number of items that have been removed from the particular partition. ### Claim 12 (depends on 1) The method of claim 1, further comprising: dynamically determining whether to partition or resize the partition-specific Bloom filter based at least in part on a number of observed false positive results with respect to the partition-specific Bloom filter. ### Claim 13 (depends on 1) The method of claim 1, wherein: the one or more other partition-specific Bloom filters corresponding to the one or more other partitions of the plurality of partitions are responsive to queries during the partitioning or resizing of the partition-specific Bloom filter. ### Claim 14 A system, comprising: a processor configured to: receive a representation of an item; use the representation to determine a particular partition with which the item is associated, wherein the particular partition with which the item is associated is one of a plurality of partitions corresponding to a volume that comprises the item, and each of the plurality of partitions have a corresponding partition-specific Bloom filter; determine whether the item is an element of a set with which the particular partition is associated, wherein the set comprises one or more objects stored in a distributed file system, and wherein the determining of whether the item is an element in the set comprises: checking a partition-specific Bloom filter corresponding to the particular partition to determine if the item is an element of the set; in response to determining that the partition-specific Bloom filter indicates that the item is not an element of the set, determining that the item is not an element of the set; and in response to determining that the partition-specific Bloom filter indicates that the item is an element of the set, querying a table associated with the set for the representation of the item, and determining that the item is an element of the set in the event that the querying of the table associated with the set indicates that the set includes the item; dynamically determine to partition or resize the partition-specific Bloom filter based at least in part on a computed probability of the partition-specific Bloom filter rendering a false positive, the computed probability being based at least in part on one or more of a filter size and a number of elements in the particular partition corresponding to the partition-specific Bloom filter; in response to determining to partition or resize the partition specific Bloom filter, partition or resize the partition-specific Bloom filter independent of one or more other partition-specific Bloom filters corresponding to the one or more other partitions of the plurality of partitions; and a storage device coupled to the processor and configured to store the partition-specific Bloom filter. ### Claim 15 (depends on 12) The system of claim 12, wherein the particular partition comprises a subset of the set. ### Claim 16 (depends on 12) The system of claim 12, wherein the representation comprises a hash. ### Claim 17 (depends on 12) The system of claim 12, wherein item comprises a chunk included in a set of one or more chunks into which a file has been segmented. ### Claim 18 (depends on 12) The system of claim 12, wherein the item comprises a chunk of data and representation comprises a hash of the chunk of data. ### Claim 19 (depends on 12) The system of claim 12, further comprising determining a number of partitions to associate with the set. ### Claim 20 A computer program product embodied in a non-transitory computer readable storage medium and comprising computer instructions for: receiving a representation of an item; using the representation to determine a particular partition with which the item is associated, wherein the particular partition with which the item is associated is one of a plurality of partitions corresponding to a volume that comprises the item, and each of the plurality of partitions have a corresponding partition-specific Bloom filter; determining, by one or more processors, whether the item is an element of a set with which the particular partition is associated, wherein the set comprises one or more objects stored in a distributed file system, and wherein the determining of whether the item is an element in the set comprises: checking a partition-specific Bloom filter corresponding to the particular partition to determine if the item is an element of the set; in response to determining that the partition-specific Bloom filter indicates that the item is not an element of the set, determining that the item is not an element of the set; and in response to determining that the partition-specific Bloom filter indicates that the item is an element of the set, querying a table associated with the set for the representation of the item, and determining that the item is an element of the set in the event that the querying of the table associated with the set indicates that the set includes the item; dynamically determining to partition or resize the partition-specific Bloom filter based at least in part on a computed probability of the partition-specific Bloom filter rendering a false positive, the computed probability being based at least in part on one or more of a filter size and a number of elements in the particular partition corresponding to the partition-specific Bloom filter; and in response to determining to partition or resize the partition specific Bloom filter, partitioning or resizing the partition-specific Bloom filter independent of one or more other partition-specific Bloom filters corresponding to one or more other partitions of the plurality of partitions. ### Claim 21 (depends on 20) The computer program product of claim 20, wherein the particular partition comprises a subset of the set. ### Claim 22 (depends on 20) The computer program product of claim 20, wherein the item comprises a chunk of data and representation comprises a hash of the chunk of data.