  Bloom filters are probabilistic data structures commonly used for approximate
membership problems in many areas of Computer Science (networking, distributed
systems, databases, etc.). With the increase in data size and distribution of
data, problems arise where a large number of Bloom filters are available, and
all them need to be searched for potential matches. As an example, in a
federated cloud environment, each cloud provider could encode the information
using Bloom filters and share the Bloom filters with a central coordinator. The
problem of interest is not only whether a given element is in any of the sets
represented by the Bloom filters, but which of the existing sets contain the
given element. This problem cannot be solved by just constructing a Bloom
filter on the union of all the sets. Instead, we effectively have a
multidimensional Bloom filter problem: given an element, we wish to receive a
list of candidate sets where the element might be.
  To solve this problem, we consider 3 alternatives. Firstly, we can naively
check many Bloom filters. Secondly, we propose to organize the Bloom filters in
a hierarchical index structure akin to a B+ tree, that we call Bloofi. Finally,
we propose another data structure that packs the Bloom filters in such a way as
to exploit bit-level parallelism, which we call Flat-Bloofi.
  Our theoretical and experimental results show that Bloofi and Flat-Bloofi
provide scalable and efficient solutions alternatives to search through a large
number of Bloom filters.
