Comparison on Search Failure between Hash Tables and a Functional Bloom Filter
Comparison on Search Failure between Hash Tables and a Functional Bloom Filter
复制标题
DOI：
10.3390/app10155218
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Hayoung Byun;Hyesook Lim
中科院分区：
文献类型：
--
作者：
Hayoung Byun;Hyesook Lim
基于散列的数据结构在许多应用中得到了广泛的应用。散列的一个内在问题是冲突，其中两个或多个元素被散列为相同的值。如果哈希表负载很重，则会发生更多冲突。由于冲突而无法存储在哈希表中的元素会导致搜索失败。已经研究了许多变体结构以减少碰撞的数量，但是没有一种结构完全解决碰撞问题。在本文中，我们声称，当哈希表负载很重时，功能性布鲁姆过滤器（FBF）提供比哈希表更低的搜索失败率。换句话说，可以用FBF代替哈希表，因为在将大量数据存储到有限大小的存储器中时，FBF在搜索失败率方面比哈希表更有效。虽然散列表除了其返回值之外还需要存储每个输入键，但是功能布隆过滤器存储没有输入键的返回值，因为根据每个输入键的不同索引组合可以用于识别输入键。在搜索失败率方面，我们从理论上比较了FBF与基于哈希的数据结构，如多哈希表，布谷鸟哈希表和D-左哈希表。我们也提供模拟结果来证明我们的理论结果的有效性。仿真结果表明，当负载因子大于0.6时，哈希表的搜索失败率大于功能布隆过滤器。
Hash-based data structures have been widely used in many applications. An intrinsic problem of hashing is collision, in which two or more elements are hashed to the same value. If a hash table is heavily loaded, more collisions would occur. Elements that could not be stored in a hash table because of the collision cause search failures. Many variant structures have been studied to reduce the number of collisions, but none of the structures completely solves the collision problem. In this paper, we claim that a functional Bloom filter (FBF) provides a lower search failure rate than hash tables, when a hash table is heavily loaded. In other words, a hash table can be replaced with an FBF because the FBF is more effective than hash tables in the search failure rate in storing a large amount of data to a limited size of memory. While hash tables require to store each input key in addition to its return value, a functional Bloom filter stores return values without input keys, because different index combinations according to each input key can be used to identify the input key. In search failure rates, we theoretically compare the FBF with hash-based data structures, such as multi-hash table, cuckoo hash table, and d-left hash table. We also provide simulation results to prove the validity of our theoretical results. The simulation results show that the search failure rates of hash tables are larger than that of the functional Bloom filter when the load factor is larger than 0.6.