Bloofi: Multidimensional Bloom filters
Bloofi: Multidimensional Bloom filters
复制标题
DOI：
10.1016/j.is.2015.01.002
复制
发表时间：
2015-12-01
影响因子：
3.7
通讯作者：
Lemire, Daniel
中科院分区：
文献类型：
--
作者：
Crainiceanu, Adina;Lemire, Daniel
布隆过滤器是一种概率数据结构，通常用于计算机科学的许多领域（网络，分布式系统，数据库等）中的近似成员问题。随着数据大小和数据分布的增加，出现了大量可用的布隆过滤器的问题，并且需要搜索所有布隆过滤器以寻找潜在的匹配。例如，在联合云环境中，每个云提供商可以使用布隆过滤器对信息进行编码，并与中央协调器共享布隆过滤器。感兴趣的问题不仅是给定的元素是否在由布隆过滤器表示的任何集合中，而且是现有集合中包含给定的元素。这个问题不能仅仅通过在所有集合的并集上构造布隆过滤器来解决。相反，我们实际上有一个多维的布隆过滤器问题：给定一个元素，我们希望收到一个元素可能所在的候选集列表。为了解决这个问题，我们考虑三种选择。首先，我们可以简单地检查许多Bloom过滤器。其次，我们建议组织的布隆过滤器在一个分层的索引结构类似于一个B+树，我们称之为Bloofi。最后，我们提出了另一种数据结构，包装的布隆过滤器在这样一种方式，利用位级并行，我们称之为Flat-Bloofi。我们的理论和实验结果表明，Bloofi和Flat-Bloofi提供了可扩展的和有效的解决方案，通过大量的布隆过滤器搜索的替代方案。爱思唯尔有限公司出版
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 of 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 also 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 three 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. Published by Elsevier Ltd.