Methods and systems to avoid false negative results in bloom filters implemented in non-volatile data storage systems
US9384126B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Sep 24, 2013 |
| Grant date | Jul 5, 2016 |
| Priority date | — |
| Expiry date | Jan 14, 2035 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99933
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.