Rank-indexed hashing: A compact construction of Bloom filters and variants
Rank-indexed hashing: A compact construction of Bloom filters and variants
复制标题
DOI：
10.1109/icnp.2008.4697026
复制
发表时间：
2008-12
期刊：
影响因子：
--
通讯作者：
Nan Hua;Haiquan Zhao;Bill Lin;Jun Xu
中科院分区：
文献类型：
--
作者：
Nan Hua;Haiquan Zhao;Bill Lin;Jun Xu
布隆过滤器及其变体已在许多网络应用中广泛使用。对于这些应用，最大限度地降低存储成本至关重要，因为这些滤波器通常需要使用稀缺且昂贵的（片上）SRAM 来实现。除了支持成员资格查询之外，布隆过滤器还被通用化以支持信息的删除和编码。尽管标准布隆过滤器结构已被证明具有极高的空间效率，但在推广时却会产生不必要的成本。已经提出了基于在哈希表中存储指纹的替代结构，其提供与某些布隆过滤器变体相同的功能，但使用更少的空间。在本文中，我们提出了一种新的指纹哈希表结构，称为Rank-Indexed Hashing，它可以实现非常紧凑的表示。提供与计数布隆过滤器相同功能的排名索引哈希结构，即使误报概率仅为 1%，也可以节省三倍或更多空间。即使对于仅支持成员资格查询的基本布隆过滤器功能，排名索引哈希结构也需要更少的空间来实现高达 0.1% 的误报概率，这一点很重要，因为标准布隆过滤器结构被广泛认为对于近似成员资格问题而言极其节省空间。
Bloom filter and its variants have found widespread use in many networking applications. For these applications, minimizing storage cost is paramount as these filters often need to be implemented using scarce and costly (on-chip) SRAM. Besides supporting membership queries, Bloom filters have been generalized to support deletions and the encoding of information. Although a standard Bloom filter construction has proven to be extremely space-efficient, it is unnecessarily costly when generalized. Alternative constructions based on storing fingerprints in hash tables have been proposed that offer the same functionality as some Bloom filter variants, but using less space. In this paper, we propose a new fingerprint hash table construction called Rank-Indexed Hashing that can achieve very compact representations. A rank-indexed hashing construction that offers the same functionality as a counting Bloom filter can be achieved with a factor of three or more in space savings even for a false positive probability of just 1%. Even for a basic Bloom filter function that only supports membership queries, a rank-indexed hashing construction requires less space for a false positive probability as high as 0.1%, which is significant since a standard Bloom filter construction is widely regarded as extremely space-efficient for approximate membership problems.