Bloom filter index for device discovery

• US 9,553,771 B1
• Filed: 03/03/2016
• Issued: 01/24/2017
• Est. Priority Date: 10/23/2015
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenna, Patrick J., O'Connor, David P., Warren, Claude N. Jr.
• Primary Examiner(s): Duong, Oanh
• Application Number:
  US15/059,599
• Time in Patent Office: 327 Days
• Field of Search: 709223-224, 707/755, 707/770, 707/797, 711/216
• US Class Current: 1/1
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 2212/251 Local memory within processor subsystem
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

Implementing a Bloom filter index as a hierarchical data structure. Bloom filters are received and their bit vectors are decomposed into successive bit sequences. For each bit sequence except the last one, memory for at least storing a pointer to a memory location on the next level is allocated on the level corresponding to the bit sequence. The pointer storage is labeled by the value of the next bit sequence. A pointer to the allocated memory is stored in the pointer storage on the previous level that was labeled by the binary value of the current bit sequence. For the last bit sequence, memory for storing Bloom filters is allocated on the last level. A pointer to the allocated memory is stored in the pointer storage on the second-to-last level that was labeled by the value of the last bit sequence. The Bloom filter is stored in the allocated memory.

Claims

1. A computer-implemented method for identifying network devices having specified traits using a multi-level hierarchical data structure, the method comprising:

receiving, by a computer, a plurality of Bloom filters representing a plurality of corresponding network devices, wherein each Bloom filter includes a bit vector with a number b of 8-bit bytes, the bit vector representing a plurality of traits of the corresponding network device;

for each received Bloom filter;

decomposing, by the computer, the bit vector into b successive bytes, wherein each successive byte corresponds to a successive level of a hierarchical data structure below level 0;

allocating, by the computer, memory on level 0 of the hierarchical data structure, the memory including a pointer storage for storing a pointer to a memory location on level 1 of the hierarchical data structure, unless such memory is already allocated based on a previously processed Bloom filter;

assigning a label to the pointer storage, based on a value of the first byte;

for each successive byte, except for the last byte;

allocating, by the computer, memory on the level corresponding to the successive byte, the memory including a pointer storage for storing a pointer to a memory location on the next successive level, unless such memory is already allocated based on a previously processed Bloom filter;

assigning a label to the pointer storage, based on a value of the next successive byte;

storing, by the computer, in the pointer storage on the previous level that was assigned a label based on the value of the successive byte, a pointer to the allocated memory, unless such a pointer has already been stored based on a previously processed Bloom filter; and

for the last byte;

allocating, by the computer, memory on the last level of the hierarchical data structure, the memory including a data storage for storing a reference to the network device, unless such memory is already allocated based on a previously processed Bloom filter;

storing, by the computer, in the pointer storage on the second-to-last level that was assigned a label based on the value of the last byte, a pointer to the allocated memory, unless such a pointer has already been stored based on a previously processed Bloom filter; and

storing, by the computer, a reference to the network device in the data storage on the last level of the hierarchical data structure;

receiving, by the computer, a search Bloom filter, wherein the search Bloom filter includes a bit vector with b bytes, the bit vector representing specified traits of a network device;

decomposing, by the computer, the search Bloom filter'"'"'s bit vector into b successive bytes, wherein each successive byte corresponds to a successive level of a hierarchical data structure below level 0; and

identifying references to network devices stored in the hierarchical data structure and related to the search Bloom filter by;

for each successive byte;

identifying, by the computer, any memory locations on the level corresponding to the successive byte, that are referenced by pointers stored on the previous level, whose assigned labels are based on the value of a byte having a 1 bit wherever the successive byte has a 1 bit; and

for the last byte;

identifying, by the computer, references to network devices data stored in the identified memory locations on the last level of the hierarchical data structure,

wherein network devices that are referenced correspond to the traits specified in the search Bloom filter.