孤惯|微软 Bing 搜索核心技术 BitFunnel 原理揭秘( 三 ) 导语从90年代中期开始

noise是我们经常用的错误概率（假阳率: Fasle Positive Rate, FPR），然而很少人去关注信噪比概念。让我们举例一些实际查询项目下的信噪比值：
信噪比给我们的启示是：假设我们查询的是"with"单词，出现的频次约为50% ，如果只有一种哈稀函数，那么它对应的信噪比分数为(0.5/((1-0.5)*${0.1}^1$)约为10.2 ，那么，当“info”单词，频率约为10%时，那么错误率与频率相等下，信噪比下降，随着频率的下降，布隆过滤器密度会突出，提高了这些稀少单词的错误率，因此就需要为这些稀少单词增加更多的哈稀函数从而才能保持与高频词一致的信噪比，举例只是到了“sawmill”单词，但现实互联网情况下，更小频率出现的单词非常多，往往需要10个以上的哈稀函数才能保持可接受的错误率。
就像查询DNA里面的特定稀少片段，传统的布隆过滤器做法是默认设置许多的哈稀函数和占用大量位数空间才能保障准确率。因此BitFunnel使用 Frequency Conscious Bloom Filter , 不同频次的单词使用不同种数的哈稀函数搜索匹配。
那么等级行在这种应用下怎么使用从而降低搜寻时间？BitFunnel结合了搜寻单词的频率和错误率的概念，提出了一种新的处理方案。
处理方案事实上就是用等级行数来关联我们单词：假设单词"with"的反向文档频率为0.29 ，那么用单条长度的原始行表示即可， “info”的为1 ，则用单条原始行还有一条1-等级行表示，后面则越稀缺的单词，其IDF越高，我们就用更多的行来表示其解决方案。你可能会问这些单词项目处理方案后面是不是存在简单的模式？然而我们也不知道具体答案，我们过去使用BF算法来通过确定的信噪比排序处理方案，同时也权衡查询时间和内存总量。最终出现了十亿中不同的解决方案，我们只评价了每种方案的IDF值，这一步花费了几秒钟，然后配置在系统中。
那么，让我们试试搜索一下“treacherous movies”是怎么进行查询的：
取出这两个单词的配置解决方案，然后将这两个解决方案组合起来获得下图（形状如漏斗）：
那么我们就可以简单直接地看出BitFunnel为什么能够这么快了：
假设行的概率密度为0.1 ，那么我们可以迅速前面四行就忽略了95%的列数。
集群间分享
【孤惯|微软 Bing 搜索核心技术 BitFunnel 原理揭秘】以上的两种概念（等级行以及 Frequency Conscious Bloom Filter）让我们节约了大量的内存空间以及提高了查询效率。现实中我们的文本物料在现在互联网上已经是一个庞大的天文数字，以前还可以在单机上处理，现在已经无法单机处理，我们需要将庞大的矩阵切割出来放到不同的集群上处理，那么我们怎么做呢？