| 主权项 |
1. A computer program product for identifying network devices having specified traits using a multi-level hierarchical data structure, the computer program product comprising:
one or more non-transitory computer-readable storage media and program instructions stored on the one or more non-transitory computer-readable storage media, the program instructions, when executed by a computer, cause the computer to perform a method comprising: receiving 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 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 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 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, 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; andfor the last byte:
allocating 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, 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; andstoring a reference to the network device in the data storage on the last level of the hierarchical data structure. receiving 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 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 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 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. |
