Persistent Bloom Filter: Membership Testing for the Entire History
Persistent Bloom Filter: Membership Testing for the Entire History
复制标题
DOI：
10.1145/3183713.3183737
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Yanqing Peng;Jinwei Guo;Feifei Li;Weining Qian;Aoying Zhou
中科院分区：
文献类型：
--
作者：
Yanqing Peng;Jinwei Guo;Feifei Li;Weining Qian;Aoying Zhou
成员测试是测试一个元素是否在一组元素中的问题。精确地执行测试在空间方面是昂贵的，需要存储集合中的所有元素。在许多应用中，通常需要可以使用小空间快速完成的近似测试。Bloom filter（BF）的设计在许多应用领域都取得了巨大的成功。但是没有支持时态查询的集合成员测试的紧凑结构，例如，人A是否在上午9：30到9：40之间访问过Web服务器？同一个人是否在上午9点45分到9点50分之间再次访问了Web服务器？使用BF来支持这种“时间成员测试”是可能的，但是我们将证明这是相当昂贵的。为此，本文设计了持久布隆过滤器（PBF），一种新的数据结构的时间成员测试与紧凑的空间。
Membership testing is the problem of testing whether an element is in a set of elements. Performing the test exactly is expensive space-wise, requiring the storage of all elements in a set. In many applications, an approximate testing that can be done quickly using small space is often desired. Bloom filter (BF) was designed and has witnessed great success across numerous application domains. But there is no compact structure that supports set membership testing for temporal queries, e.g., has person A visited a web server between 9:30am and 9:40am? And has the same person visited the web server again between 9:45am and 9:50am? It is possible to support such "temporal membership testing" using a BF, but we will show that this is fairly expensive. To that end, this paper designs persistent bloom filter (PBF), a novel data structure for temporal membership testing with compact space.