计数布隆过滤器

基本概念

计数布隆过滤器被定义为布隆过滤器的一种泛化数据结构，用于在给定一系列元素时测试给定元素的计数是否小于给定阈值。作为布隆过滤器的一种泛化形式，它存在误报的可能性，但没有误判的可能性——换句话说，查询要么返回“可能高于或等于阈值”，要么返回“肯定低于阈值”。

算法描述

  • 计数布隆过滤器中使用的大多数参数与布隆过滤器中的定义相同，例如 n、k。m 表示计数布隆过滤器中计数器的数量，它是布隆过滤器中 m 位的扩展。
  • 一个空的计数布隆过滤器被设置为 m 个计数器，所有计数器都初始化为 0。
  • 与布隆过滤器类似，也必须定义 k 个不同的哈希函数，每个函数负责将某个集合元素映射或哈希到 m 个计数器数组位置中的一个，从而创建均匀的随机分布。k 也是一个常数，远小于 m，它与要追加的元素数量成正比。
  • 布隆过滤器的主要泛化是追加元素。要追加元素，将其插入到 k 个哈希函数中的每一个函数中以获得 k 个数组位置，并在所有这些位置将计数器加 1。
  • 要查询具有阈值 θ 的元素（验证元素的计数是否小于 θ），将其插入到 k 个哈希函数中的每一个函数中以获得 k 个计数器位置。
  • 如果这些位置中的任何一个计数器小于 θ，则元素的计数肯定小于 θ——如果它更高或等于，则所有相应的计数器都将高于或等于 θ。
  • 如果所有计数器都高于或等于 θ，则计数确实高于或等于 θ，或者计数器碰巧高于或等于 θ。
  • 即使计数小于 θ，如果所有计数器都高于或等于 θ，则这种情况被定义为误报。与布隆过滤器一样，这也应该最小化。

更新于: 2020年1月3日

449 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告