Bloom filters are simple, space-efficient data structures used wherever membership checks need to be performed. However, such checks may result in false positives. The false positive rate depends on only three parameters. This study empirically examines the impact of indi-vidual parameters on various Bloom filter variants (Standard-, Dual-, and Cross-Checking-Bloom filters). The findings reveal that the Cross-Checking-Bloom-Filter shows the lowest false positive rate.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Empirical Comparison of Different Bloom Filter Variants

  • Jürgen Lenfant

摘要

Bloom filters are simple, space-efficient data structures used wherever membership checks need to be performed. However, such checks may result in false positives. The false positive rate depends on only three parameters. This study empirically examines the impact of indi-vidual parameters on various Bloom filter variants (Standard-, Dual-, and Cross-Checking-Bloom filters). The findings reveal that the Cross-Checking-Bloom-Filter shows the lowest false positive rate.