BLOOM FILTER INDEX FOR DEVICE DISCOVERY

摘要

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.

主权项

1. A computer-implemented method for implementing a Bloom filter index as a multi-level hierarchical data structure, the method comprising:
receiving, by a computer, one or more Bloom filters, each including a bit vector having a predefined length; processing each received Bloom filter by: decomposing, by the computer, the Bloom filter's bit vector into two or more successive bit sequences, based on a predefined pattern of bit sequence lengths, each successive bit sequence corresponding 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 the binary value of the first bit sequence; for each successive bit sequence, except for the last bit sequence:
allocating, by the computer, memory on the level corresponding to the successive bit sequence, 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 the binary value of the next successive bit sequence;storing, by the computer, in the pointer storage on the previous level that was assigned a label based on the binary value of the successive bit sequence, 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 bit sequence:
allocating, by the computer, memory on the last level of the hierarchical data structure, the memory including a data storage for storing a Bloom filter and/or associated data, 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 binary value of the last bit sequence, a pointer to the allocated memory, unless such a pointer has already been stored based on a previously processed Bloom filter; andstoring, by the computer, the Bloom filter and/or associated data in the data storage on the last level of the hierarchical data structure.