Considering multiple lookups in bloom filter decision making
View Patent ↗Example apparatus, methods, and computers are configured to consider multiple lookups when making decisions concerning whether a probabilistic data structure indicates that an item is or is not present. One example method includes receiving a first response from a probabilistic data structure, where the first response indicates whether a first element is a member of a set of stored elements. The example method also includes receiving a set of second responses from the probabilistic data structure, where the set of second responses indicate whether members of a corresponding set of second elements are members of the set of stored elements. The method then provides a present/absent signal concerning whether the first element is a member of the set of stored elements. The signal is computed as a function of the first response and the set of second responses rather than merely as a function of the first response.
1. An apparatus, comprising:
a processor;
a memory;
a set of logics comprising a first logic and a second logic; and
an interface to connect the processor, the memory, and the set of logics,
the first logic being configured to provide a value associated with the probability that a data sub-block processed by a data de-duplication logic is a member of a set of data sub-blocks stored by the data de-duplication logic, the value being provided in response to a lookup of a key value in a probabilistic data structure that stores information concerning members of the set of data sub-blocks, the key value being associated with a data sub-block, the key value being a de-duplication hash of the element, the probabilistic data structure being a Bloom filter, the Bloom filter being stored in the memory; and
the second logic being configured to provide a present/absent signal indicating whether a data sub-block is present or absent in the set of data sub-blocks, where the present/absent signal is computed as a function of two or more values provided by the first logic, where one of the two or more values is directly related to the data sub-block and at least one of the two or more values are indirectly related to the data sub-block.
2. The apparatus of claim 1 , where the function of two or more values is of the form:
F ( sb )= F (lookup( sb ), lookup( sb −), lookup( sb +))
where:
F(sb) is a function upon whose value a present/absent decision can be made,
lookup(x) is function whose value indicates whether the key value x is found in the Bloom filter,
sb is the sub-block for which the present/absent signal is to be provided,
sb− is zero or more sub-blocks processed by the data de-duplication logic before processing sb, and
sb+ is zero or more sub-blocks processed by the data de-duplication logic after processing sb.
3. The apparatus of claim 2 , where F(sb) can yield a result indicating that sb is not present in the set of elements when a result from lookup(sb) indicates that sb is present in the set of elements.
4. The apparatus of claim 3 , where F(sb) cannot yield a result indicating that sb is present in the set of elements when a result from lookup(sb) indicates that sb is not present in the set of elements.
5. The apparatus of claim 1 , where the function is of the form:
F
(
sb
)
=
lookup
(
sb
)
+
∑
i
=
1
After
(
lookup
(
sb
i
)
*
wa
i
)
+
∑
j
=
1
Before
(
lookup
(
sb
i
)
*
wb
j
)
where:
F(sb) is a function upon whose value a present/absent decision can be made,
lookup(x) is function whose value indicates whether the key value x is found in the probabilistic data structure,
After is the number of lookups after lookup(sb) to be considered,
Before is the number of lookups before lookup(sb) to be considered,
wa i is a weight for a lookup after lookup(sb), and
wb j is a weight for a lookup before lookup(sb).
6. The apparatus of claim 5 , where one or more of, After, Before, wa i and wb j are dynamically configurable based, at least in part, on one or more of, sub-block size, a false positive rate, and data entropy.
7. The apparatus of claim 1 , where the function is configured to produce fewer false positives than would be produced if only one value provided by the first logic was considered.
8. The apparatus of claim 1 , the set of logics comprising:
a third logic configured to store patterns produced by multiple logics; and
a fourth logic configured to make a present/absent determination for a sub-block based, at least in part, on the stored pattern.
9. The apparatus of claim 1 , where the probabilistic data structure uses less than 1.44 log 2(1/e) bits of space per key stored in the probabilistic data structure, e being the false positive rate for the probabilistic data structure.
10. A non-transitory computer-readable medium storing computer executable instructions that when processed by a computer control the computer to perform a data de-duplication method, the method comprising:
receiving a first response from a probabilistic data structure, where the first response indicates whether a first element is a member of a set of stored elements;
receiving a set of second responses from the probabilistic data structure, where the set of second responses indicate whether members of a corresponding set of second elements are members of the set of stored elements; and
providing a present/absent signal concerning whether the first element is a member of the set of stored elements, where the signal is computed as a function of the first response and the set of second responses, the probabilistic data structure being a Bloom filter.
11. The non-transitory computer-readable medium of claim 10 , where the first element is a data sub-block being processed by a data de-duplication logic, where members of the set of stored elements are data sub-blocks stored by the data de-duplication logic, and where members of the set of second elements are data sub-blocks processed by the data de-duplication logic.
12. The non-transitory computer-readable medium of claim 11 , where the set of second elements includes one or more of, data sub-blocks processed before the first element, and data sub-blocks processed after the first element.
13. The non-transitory computer-readable medium of claim 12 , where the significance of a member of the set of second elements to the present/absent signal varies directly with the number of sub-blocks processed in between when the member of the second set of elements was processed and when the first element was processed.
14. The non-transitory computer-readable medium of claim 10 , comprising selectively determining that the first element is not a member of the set of stored elements even though the first response indicates that the first element is a member of the set of elements upon determining that more than a threshold number of the set of second responses are negative responses.