Bloom filter with memory element
View Patent ↗Techniques are provided for determining if an element is contained in a set of elements. In one aspect, an element may be received and inserted into a bloom filter. The element may also be inserted into a memory associative on the bloom filter indexes. In another aspect, a search element may be received and compared to a bloom filter. If the search element is included in the bloom filter, a memory may be used to determine if the search element is included in the set of elements.
1. A method comprising:
receiving a search element;
computing bloom filter indexes for the search element;
comparing the computed bloom filter indexes to a plurality of bloom filters to determine if the search element is not included in a set of elements; and
when the search element is not indicated as not being included in the set of elements, comparing the search element to a memory to determine if the search element is included in the set of elements.
2. The method of claim 1 wherein the computed bloom filter indexes are an ordered set of indexes.
3. The method of claim 2 wherein comparing the search element to the memory further comprises:
determining, using a content addressable memory associative on the ordered set of indexes, that an entry exists for the ordered set of indexes; and
determining that the search element is associated with the entry, wherein an associated search element indicates the search element is included in the set of elements.
4. The method of claim 2 wherein comparing the search element to the memory further comprises:
determining, using a content addressable memory associative on the search element, that an entry exists for the search element, wherein the existing entry indicates the search element is included in the set of elements.
5. The method of claim 2 wherein comparing the bloom filter indexes to the memory further comprises:
computing a hash of the ordered set of indexes;
retrieving an entry from the memory, wherein the entry to retrieve is based on the hash; and
determining that the search element is associated with the retrieved entry, wherein the associated search element indicates the search element is included in the set of elements.
6. A device comprising:
a hardware processor to execute:
receive logic to receive a search element;
bloom filter index logic to compute a plurality of bloom filter indexes for the search element;
first compare logic to compare the plurality of bloom filter indexes to a plurality of bloom filters to determine if the search element is not included in a set of elements; and
second compare logic to compare a memory associative on the plurality of bloom filter indexes to the search element when the plurality of bloom filters do not indicate that the search element is not included in the set of elements;
wherein inclusion of the search element in the memory indicates the search element is in the set of elements.
7. The device of claim 6 wherein omission of the search element from the memory indicates the search element is not in the set of elements.
8. The device of claim 7 wherein execution of the receive logic further causes the processor to receive an insertion element, and wherein the processor is further to execute:
hash logic to further compute a plurality of bloom filter indexes for the insertion element; and
insert logic to (i) insert the plurality of bloom filter indexes computed for the insertion element into the plurality of bloom filters, and (ii) store the insertion element in the memory associative on the plurality of bloom filter indexes computed for the insertion element.
9. The device of claim 8 wherein the memory is associative on the plurality of bloom filter indexes computed for the insertion element via a content addressable memory.
10. The device of claim 8 wherein the memory is associative on the plurality of bloom filter indexes computed for the insertion element via a hash.