BLOOM FILTER WITH MEMORY ELEMENT

• US 20140344934A1
• Filed: 05/17/2013
• Published: 11/20/2014
• Est. Priority Date: 05/17/2013
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Jorgensen, Steven Glen
• Granted Patent: US 9,171,153 B2
• Time in Patent Office: Days
• US Class Current: 726/24
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 21/56 Computer malware detection or handling, e.g. anti-virus arrangements
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms

Abstract

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.

Claims

1. A method comprising:

receiving an element to be included in a set of elements;

computing a plurality of bloom filter indexes based on the element;

inserting the element into a plurality of bloom filters using the plurality of bloom filter indexes; and

storing the element in a memory, wherein the element is accessed in the memory to eliminate false positives.

2. The method of claim 1 wherein the plurality of bloom filter indexes is an ordered set of indexes.

3. The method of claim 2 wherein storing the element in the memory further comprises:

locating an empty entry in the memory, wherein at least a portion of the entry is a content addressable memory;

storing the ordered set of bloom filter indexes in the content addressable memory portion of the located entry; and

storing the element associated with the located entry.

4. The method of claim 2 wherein storing the element in the memory further comprises:

locating an empty entry in the memory, wherein at least a portion of the entry is a content addressable memory; and

storing the element in the content addressable memory portion of the located entry.

5. The method of claim 2 wherein storing the element in the memory further comprises:

computing a hash of the ordered set of indexes;

identifying the memory associated with the hash; and

adding the element to the identified memory.

6. 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 indicted 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.

7. The method of claim 6 wherein the computed bloom filter indexes are an ordered set.

8. The method of claim 7 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.

9. The method of claim 7 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.

10. The method of claim 7 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.

11. A device comprising:

receive logic to receive a search element;

bloom filter index logic to compute a plurality of bloom filter indexes for the search element;

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

compare logic to compare a memory associative on the 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.

12. The device of claim 11 wherein omission of the search element from the memory indicates the search element is not in the set of elements.

13. The device of claim 12 further comprising:

the receive logic to further receive an insertion element;

the hash logic to further compute a plurality of bloom filter indexes for the insertion element; and

insert logic to insert the plurality of bloom filter indexes computed for the insertion element into the plurality of bloom filters, the insertion logic further configured to store the insertion element in the memory associative on the bloom filter indexes computed for the insertion element.

14. The device of claim 13 wherein the memory is associative on the plurality of bloom filter indexes via a content addressable memory.

15. The device of claim 13 wherein the memory is associative on the plurality of bloom filter indexes via a hash.