布隆过滤器计数的假阴性问题

布隆过滤器是有效，节省空间的数据结构，用于简洁地表示数据集并支持近似成员资格查询。 传统上，研究人员通常认为，Bloom过滤器有可能返回假阳性，但在行为良好的操作下绝不会返回假阴性。 但是，通过研究主流变体，我们发现Bloom过滤器在许多情况下的确会返回假阴性。 在这项工作中，我们证明了误报项的不可检测的错误删除和多地址项的可检测的错误删除是Bloom过滤器中误报的两个常见原因。 然后，我们在理论上和实践上测量电位并暴露假阴性。 受潜在的假阴性通常不会完全暴露的事实的启发，我们提出了一种新颖的布隆过滤器方案，该方案将设置的位比率提高到大于1的值，而又不降低设置为零的比率。 数学分析和综合实验表明，该设计可以减少暴露的假阴性的数量，并减少假阳性的可能性。 据我们所知，这是在支持项目插入，查询和删除操作的标准用法时，系统地处理Bloom过滤器的误报和误报问题的第一篇工作。