Bloom filter index for device discovery

Abstract

A Bloom filter index is implemented as a multiway tree that stores Bloom filters having a predefined number of N-bit sequences. Nodes are labeled with portions of the N-bit sequences and non-leaf tree nodes may have up to 2children. All children of a given node have labels that are the same length. Bloom filters are inserted recursively, starting at a first non-leaf node, based on a node label matching an initial N-bit sequence of the Bloom filter. If a given node is full, its child nodes are split, resulting in fewer than 2new child nodes, each labeled with different initial N-bit sequence of the original child node, which becomes a child node of a new node with label the remaining bits in the label of the original child node. The recursive insert procedure is then performed to insert the Bloom filter in the given node.