首页 体育 教育 财经 社会 娱乐 军事 国内 科技 互联网 房产 国际 女人 汽车 游戏

Bing搜索核心技术BitFunnel原理

2020-01-13

导语 从90年代中期开端,人们遍及知道,关于内容索引来说,文件签名技能比反向链接作用更差。最近几年必应查找引擎开发与布置了一套依据位切开的标签索引。这种索引代替了之前的依据反向索引的出产体系。这项搬运背面驱动的要素是反向链接需求作业存储价值。本篇内容将叙述这项算法上的立异创造,改动传统上在云核算框架上被以为无法运用的技能。BitFunnel算法直接处理四项根底位切开块签名的约束。一起,算法的映射进入集群供给了防止和其他签名联络的价值。这儿会先展现这些立异产生了比传统位切开签名的更明显的功率进步,然后将会进行BitFunnel与分块化Elias-Fano索引,MG4J,和Lucene等的比照。本文依据论文《BitFunnel: Revisiting Signatures for Search》和Bing团队实践共享视频,对BitFunnel原理进行剖析解读。

问题布景

假定咱们一篇十分短的文档:内容仅仅“big brown dog”这三个单词,咱们可以用固定长度的位向量对这组单词进行编码,也称固定长度的位向量为 文档签名 或许 布隆过滤器 。简略样例这儿采取了十六位长度的位向量来进行操作,当然,在Bing体系上不会用这么短的位向量,往往运用五千个以上的来进行表明。一开端,位向量全都是空的,由于还没有进行数据的加载操作。

布隆过滤器初始化会设置哈稀函数的种数,哈稀函数是为了让文档单词对应到位向量的固定方位上。这儿我运用了三种不同的哈稀函数来映射。映射成果如下:

从上图可知,每个单词都对应着位向量上面的三个方位上置1,然后咱们得到了这份简易文档的文档签名,假定咱们要查找“cat”单词在不在这份文档里边,咱们只需求查询“cat”单词经过哈稀函数映射出来的三个方位上是否都为1就可以进行断定了,很明显,有一个不为1,所以“cat”单词并不在这份文档里边。

当咱们查找 big“单词时,咱们会发现三个方位均置为1,那么咱们可以断定“big”是这份文档的或许成员。如下图所示:

仔细的你必定注意到这儿用了或许两个字,为什么是或许成员呢?下图是咱们查找的是“house”单词的成果:

咱们会发现这个单词的一切映射方位也都是1,但实践上咱们知道文档里并没有“house”单词,这个存在的原因是由于有哈稀函数映射磕碰的存在,导致其他的方位也有相对应的1在文档里边弥补了没有为1的状况,这也是咱们为什么要用多种哈稀映射函数的原因,可以下降这种过错率。

依据这样的结构咱们,假定咱们存储有十六篇文档:A-P,顺次建立了签名,那么有查找需求:Query文档进来,经过下列查询就可以得到或许匹配文档:

这样的思路无疑是十分直观简略且简略完结的,可是在网络中存储的那些网页,根本需求几千位长度的位向量去表明,假如咱们每一篇文档都这样去查询匹配,假定咱们有N篇文章,用了P个位的文档签名符号,咱们的核算机CPU每次处理的位数为64位,那么查询一篇文章需求花费的价值便是 N*单位时刻。

这样的价值无疑是十分昂扬的,由于现在文章的数量和长度乘积无疑是一个天文数字。一个十分奇妙的方法便是将这个矩阵回转过来,队伍倒置,那么咱们的存储由N*P队伍矩阵就变成了P*N,很显然,P远远小于N。那么,咱们的查询文档Query对应的只需求去匹配其间位为1的对应的文档的行向量即可,进程如下:

从上图流程可以看出,对应的只需求查询对应为1的位向量行数的文章的状况就可以了,假定实在中查询的文档Query的为1位数是W位,在实践查询中,W往往是少量几个单词去查询,W远远小于P,对应列进行并运算,成果为1则该篇方位或许匹配,这样查询速度就大大进步。可是,还有一个问题便是实践中 N 的数量也十分巨大。

那么这点怎样处理呢?这就引进了今日要讲的要点算法:BitFunnel。

BitFunnel创造

等级行


等级行是原始行的简略紧缩版别,可以进步过滤速度,但一起也带来了更高的过错率,让咱们看看等级行是怎样运转的。咱们将原始行称为0-等级行,假定原始行是32位长度,那么1-等级行便是由0-等级行对等截成两半进行或运算取得,那么长度就下降了一半,更高等级行依此进行核算取得,如下图举例所示:

那么现在咱们怎样运用咱们获取的等级行呢?假定咱们有3行32列需求匹配处理,那么咱们可以考虑将榜首行紧缩成2-等级行,第二行紧缩成1-等级行,第三行坚持不变。假如咱们没有这样做,咱们需求将3*32=96位悉数放进内存进行查询处理才干够完结。而现在,=56位,详细如下图所示:

那么查询的时分,咱们先将得出榜首行和第二行的并运算成果,仅两列需求去与第三行在进行处理,然后平移到第三行另一边处理,再将榜首行移动到第二行的别的一边,这时分也是两列均为1呈现,然后与第三行处理,再搬运回去处理终究一次即可得出成果,四次处理核算流程如下:

以上这样的处理咱们可以很多地运用中心成果加速核算。

频率布隆过滤器

传统的布隆过滤器需求花费超长度的位向量才干做到满意较低的过错率,而BitFunnel则运用频率布隆过滤器来下降内存总量。什么是频率布隆过滤器?当咱们在布隆过滤器中查询仅仅查询一个项目时,假定整个布隆过滤器为1的密度为10%,那么当咱们只运用一个哈稀函数,那么对应的磕碰率为10%,那么跟着咱们哈稀函数品种的添加,咱们可以核算出过错率,d为布隆过滤器的概率密度,但这儿咱们可以进一步提出新的概念信噪比:

noise是咱们经常用的过错概率,可是很少人去重视信噪比概念。让咱们举例一些实践查询项目下的信噪比值:

信噪比给咱们的启示是:假定咱们查询的是 with 单词,呈现的频次约为50%,假如只要一种哈稀函数,那么它对应的信噪比分数为*${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%的列数。

集群间共享

以上的两种概念让咱们节省了很多的内存空间以及进步了查询功率。实践中咱们的文本物料在现在互联网上现已是一个巨大的天文数字,曾经还可以在单机上处理,现在现已无法单机处理,咱们需求将巨大的矩阵切开出来放到不同的集群上处理,那么咱们怎样做呢?

假定咱们仍是一共有十六篇文档和十六位的表明,那么矩阵表明为16*16,一起咱们回转得到了十六位*十六篇,咱们可以知道,短文章的文档里边为1的个数仍是适当少的,归于稀少矩阵,会糟蹋适当大的空间存储,而长篇的文章里边1的个数适当高,其对应的过错率也很高。在BitFunnel中,集群间按不同文章的长度进行切开共享,下面比如切开成了三部分,实践上会按其他十到十五种不同组。

当按长度分好组后,咱们就可以对稀少部分进行紧缩存储,密布的文章进行扩大位数存储,下降过错率。

那么随之咱们跟之前相同就可以,当咱们的查询文档Query对应只要三位为1是,咱们别离对这三组的对应行求与运算即可得出成果:

这样的核算方法实践上在90年代的时分就提出来了,可是一向不被认可。为什么?其时遍及都仍是在单个核算机上进行各种算法操作,那么在一台机器上又将数据如上图相同切开成三部分别离进行处理很明显价值因小失大。本来只需求进行一遍操作的流程被复杂化了,并且事实上也不仅仅切开成三部分,往往是十几类。而跟着年代的开展,咱们现在具有了分布式的集群,咱们可以将不同的机器处理不同文章长度品种的文档:

其次还有不同的是内存技能的开展,曾经咱们用每GB的花费金钱来衡量其间的成本是过错的方法:

传统衡量方法上,硬盘取得存储1GB的空间只需求0.05美元,而DDR4需求7.44美元,导致了很多企业以为可以添加存储就不断往硬盘上堆积,但这种方法很明显是过错的。

假定公司有存储数据总量为D,然后服务上需求查询的文档总量设置为Q,假如咱们运用快速的机器,Q个查询很快就完结了:

假如咱们用存储大可是处理速度慢的机器,咱们仍需求遍历一切的数据才干取得想要的数据总量:

假如咱们选用BitFunnel的方法来处理,那么,查询量Q可以用表明,引进这样的概念就可以讲之前硬盘和DDR4换一种核算方法,用每秒查询带宽量以及每美金每秒查询带宽量来表明之间才干不同,成果如下:

咱们需求179倍的硬盘才干比得上DDR4,价格是DDR4的76倍价值。

终究咱们来聊聊怎样处理过错率,传统上咱们为了下降匹配过错率大幅度地进步了存储价值。这样做真的有意义么?实践上咱们网页查找的方针并不是获取与关键词真的都彻底匹配的网页,而是获取到内容最相契合的网页。必应有一个Ranking Oracle体系,可以核算一个查询和文档之间的契合分数来衡量文档与用户方针的价值。这个体系考虑了上千种信号进行处理,乃至其间一些都不知道它是怎样起作用的,由于这是依据机器学习在高维空间中学习所获取的成果,一起也十分运转的价值也适当高。

假定咱们有无限的查询时刻和查询物料传送给Ranking Oracle,让它回来十项最相关的文档资料,这将怎样处理?走运的是,咱们有很好的处理计划。Bellevue Washington有一个大厦里边有上千名的工程师,他们的首要作业便是防止网络传来相同的文档,首要战略的技能是经过过滤那些不能匹配布隆过滤器的文件。

在BitFunnel创造之前,首要选用反向索引。 选用了BitFunnel之后运转的速度更快, 但也同样会生成过错样本传递Ranking Oracle,BitFunnel之所以胜出在于可以将过错样本变少的一起确保时刻功率。

比照

可以看出:BitFunnel的优势在于速度和DQ低,可是有必定的过错率。

终究,是Bing运用BitFunnel后的作用图:

期望各位技能牛人可以从这Bing查找BitFunnel技能完结文章中收成并运用到实践作业中。

[1] BitFunnel: Revisiting Signatures for Search,Bob Goodwin,Michael Hopcroft,Dan Luu,SIGIR 2017  https://www.youtube.com/watch?v=1-Xoy5w5ydM

[2] An Experimental Study of Bitmap Compression vs. Inverted List Compression, Wang, Jianguo and Lin, Chunbin and Papakonstantinou, Yannis and Swanson, Steven, SIGMOD 2017

[3] Weighted bloom filter. Jehoshua Bruck, Jie Gao, and Anxiao Jiang. In 2006 IEEE International Symposium on Information theory. IEEE.

[4] BitFunnel官方博客: http://bitfunnel.org/

热门文章

随机推荐

推荐文章