Methods and systems to avoid false negative results in bloom filters implemented in non-volatile data storage systems
First Claim
1. A data processing method, comprising:
- at a non-volatile data storage system;
receiving from a host a first element for testing with respect to a Bloom filter, wherein the Bloom filter is stored in a non-volatile storage medium of the non-volatile data storage system;
testing whether the first element is present in the Bloom filter, by;
processing the first element with k distinct hash functions to generate a first set of k bit positions in the Bloom filter, where k is an integer greater than 2;
reading the first set of k bit positions from the Bloom filter;
returning a first result in accordance with a determination that at least k minus x (k−
x) bit positions in the Bloom filter from the first set are set, where x is an integer greater than zero and less than k; and
returning a second result in accordance with a determination that y or more of the k bit positions in the Bloom filter from the first set are not set, where y is equal to x plus one (x+1).
3 Assignments
0 Petitions
Accused Products
Abstract
The various implementations described herein include systems, methods and/or devices used to avoid false negative results in Bloom filters implemented in non-volatile data storage systems. In one aspect, if an element is added to a Bloom filter using k hash functions, instead of requiring all k bits to be set before returning a positive result (e.g., indicating that the element is most likely present in the Bloom filter), the embodiments described herein return a positive result when at least k minus x (k−x) bit positions are set in the Bloom filter, where x is an integer greater than zero and less than k. In some embodiments, additional measures to avoid false negatives include performing a read check immediately after setting the k bits in the Bloom filter and/or using a conservative reading threshold voltage.
428 Citations
30 Claims
-
1. A data processing method, comprising:
at a non-volatile data storage system; receiving from a host a first element for testing with respect to a Bloom filter, wherein the Bloom filter is stored in a non-volatile storage medium of the non-volatile data storage system; testing whether the first element is present in the Bloom filter, by; processing the first element with k distinct hash functions to generate a first set of k bit positions in the Bloom filter, where k is an integer greater than 2; reading the first set of k bit positions from the Bloom filter; returning a first result in accordance with a determination that at least k minus x (k−
x) bit positions in the Bloom filter from the first set are set, where x is an integer greater than zero and less than k; andreturning a second result in accordance with a determination that y or more of the k bit positions in the Bloom filter from the first set are not set, where y is equal to x plus one (x+1). - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
12. A non-volatile data storage system, comprising:
-
a non-volatile storage medium storing a Bloom filter; one or more processors; and memory storing one or more programs, which when executed by the one or more processors cause the non-volatile data storage system to; receive from a host a first element for testing with respect to a Bloom filter, wherein the Bloom filter is stored in a non-volatile storage medium of the non-volatile data storage system; test whether the first element is present in the Bloom filter, by; processing the first element with k distinct hash functions to generate a first set of k bit positions in the Bloom filter, where k is an integer greater than 2; reading the first set of k bit positions from the Bloom filter; returning a first result in accordance with a determination that at least k minus x (k−
x) bit positions in the Bloom filter from the first set are set, where x is an integer greater than zero and less than k; andreturning a second result in accordance with a determination that y or more of the k bit positions in the Bloom filter from the first set are not set, where y is equal to x plus one (x+1). - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
23. A non-transitory computer readable storage medium storing one or more programs configured for execution by one or more processors of a non-volatile data storage system, the one or more programs comprising instructions for causing the non-volatile data storage system to:
-
receive from a host a first element for testing with respect to a Bloom filter, wherein the Bloom filter is stored in a non-volatile storage medium of the non-volatile data storage system; test whether the first element is present in the Bloom filter, by; processing the first element with k distinct hash functions to generate a first set of k bit positions in the Bloom filter, where k is an integer greater than 2; reading the first set of k bit positions from the Bloom filter; returning a first result in accordance with a determination that at least k minus x (k−
x) bit positions in the Bloom filter from the first set are set, where x is an integer greater than zero and less than k; andreturning a second result in accordance with a determination that y or more of the k bit positions in the Bloom filter from the first set are not set, where y is equal to x plus one (x+1). - View Dependent Claims (24, 25, 26, 27, 28, 29, 30)
-
Specification