search

linvon / cuckoo-filter

Cuckoo Filter go implement, better than Bloom Filter, configurable and space optimized 布谷鸟过滤器的Go实现，优于布隆过滤器，可以定制化过滤器参数，并进行了空间优化
MIT License
294 stars 27 forks source link

什么是半排序桶，我应该如何去理解，类比什么事物 #7

Closed GuoxinL closed 2 years ago

GuoxinL commented 2 years ago

什么是半排序桶，我应该如何去理解，类比什么事物

linvon commented 2 years ago

可以参考实战指南中提到的第二点解释 半排序是将原来桶中可能存储的内容值的所有情况做了枚举后，按照排列组合顺序排序。这样只需要在桶中存储对应值的序号而不用存储具体的值。在一定场景下存储序号可以比存储值少占用一个bit，类似于存储了一个索引

GuoxinL commented 2 years ago

image 您的指南挺清晰的，在调优方面解决了当下的问题。 before image after image 但是我仍然有一个问题，指南中提到的负载因子是如何得来的，为什么size的大小要遵循这个公式size/α ~=(<) 2^n

linvon commented 2 years ago
  1. 负载因子是当达到这个阈值时插入成功率会急剧劣化，这个受影响于hash算法与过滤器的设计，具体数值的来源都是由原论文作者经过实验得出的
  2. 桶的大小必须满足为2的指数倍，因此size/α代表的真正存储的数量级应该小于且无限接近桶大小，否则就算比当前桶大小大了1，那也需要将桶大小翻倍才能存储这些数据，会造成很多不必要的空间浪费
GuoxinL commented 2 years ago

感谢作者的回复

GuoxinL commented 2 years ago

计算假阳性概率的公式是2b/2^f< r但是假阳性的概率不是随着过滤器的项增多，假阳性的概率不断的增大；这个公式计算的是什么时候的假阳性概率

linvon commented 2 years ago

假阳性率本质上是通过hash计算后位置冲突的概率，这与过滤器本身的属性有关，与已插入的项数无关。你所描述的应该是插入时产生错误冲突的概率，这个概率应该在桶满时等于假阳性率

GuoxinL commented 2 years ago

感谢您的回复

GuoxinL commented 2 years ago

感谢您的回复