[第002号]
Bing搜索引擎.png
摘要
自从90年代中期以来，大家普遍认为签名文件在各个方面败落与索引文件在文档索引方面。在最近几年Bing搜索引擎开发和部署了一套基于bit-sliced signatures，这种索引技术被称作BitFunnel，取代了原先基于倒排索引（inverted index）的产品系统。从倒排索引却换到当前方式背后驱动因素是运营成本的节省。这篇论文描述了算法的创新和改变，在云计算环境下让我们有机会去重新审视那些过去被认为不能使用的技术。BitFunnel算法解决了bit-sliced block signatures的四个基本的限制。与此同时，我们把算法映射到集群上也给我们提供了机会去避免伴随签名的其他的代价。我们在接下来展示了这种创新产生的明显的性能相比较于传统的bit-sliced signatures，而且比对BitFunnel与Partitioned Elias-Fano Indexes，MG4J和Lucene。
研究过程
1. 介绍
基于签名的方法会带来四个挑战；
（1）确定一个term是否匹配，需要检查现有集合中的所有文档。相比于倒排索引需要消耗更多的CPU和内存资源。
（2）签名需要足够长为了满足可接受的false positive rate，即使是搜索最不常见的terms。
（3）网络文档长短差异很大，而受限于布隆过滤器和可接受的false positive rate的原因，签名必须足够长容纳最长的文档。
（4）基于签名的格式配置不容易理解。
作者提出了一系列的技术来应对这些挑战；
（1）引入higher rank row解决查询执行的时间。
（2）引入frequency-conscious signatures来减少内存空间。
（3）全集分级来减少文档大小差异。
（4）开发了一套系统性能代价模型并使用该模型高效的定义有约束的最优化配置。
2. 背景和前期工作
2.1 倒排索引（Inverted Indexes）
倒排索引原理.png
2.2 Bit-String Signatures
对term使用多个hash函数进行计算，计算结果的所在位置设置为1。
Bit-String Signatures.png
2.3 Bit-Slice Signatures
BitFunnel重新定义的签名文件。签名，顾名思义，就是对需要索引的每个文档进行一个签名。在BitFunnel中，签名表示为文档中的一系列term的集合，用bloom filter表示。假设每个term用一个bit vector表示，那么整个文档的签名就是它包含所有term的union，对于query来说，它的签名也是一样的定义。如同bloom filter定义，这些term的bit vector从hash函数产生，假如所有的签名都基于同样的hash函数，那么所有的签名就是等长的，把这些签名按照列组织在一起，就是签名文件的bit-slice的布局，可以进行多文档检索。下图是一个16bit的多文档以及query签名文件格式。
多文档检索，加快并行处理速度
Bit-Slice Signatures.png
2.4 Bit-Slice Blocked Signatures
Bit-Sliced布局的问题在于，如果查询的term非常稀疏，那么代价就比较高昂，因为也需要对每个文档的所有bit扫描才可以得出结果，因此一种改进是Bit-Sliced Block签名，理念是让多个文档的签名共享一列，共享的文档数被成为block factor，这样可以缩短行的长度，但却是以增加false positive为代价的。这种技术增加了复杂度但是带来的收益不大。
3. BitFunnel系统
3.1 架构概览
Bing维护一个多份、异地备份的网络索引，每一个都被切分成BitFunnel节点集群。下图显示的是一个单一集群，查询是分布式的，每一个节点收到查询请求之后，把他解析成一个抽象语法树，重写树到可执行计划中然后在本地编译，然后将编译后的计划广播到剩下的集群，集群中的节点是并行的运行编译的计划，返回结果到计划节点进行聚合。这些结果被传递到其他系统，对满足条件的文档进行打分并返回给用户。
BitFunnel集群.png
3.2 False Positive的代价
False Positive.png
对于网络搜索的场景False Positive是可以接受的。
4. BitFunnel创新点
4.1 Higher Rank Rows
BitFunnel的第一个工作是让block factor不固定，也就是每个term是用不同的block factor hash到多个Bit-Sliced Block签名文件中，具体来说，block factor是2的整数幂，同时引入一个概念叫做row rank，表示block factor的幂指数。因此row rank为0跟row rank为r的签名文件的对应列的文档的关系为：
row rank关系
其中w为机器的字宽的对数，例如64bit机器的w为6。举栗来说，假如w为2，有3个row rank分别为0，1，2的Bit-Slice Block签名文件，那么rank=1的签名文件中第4列的文档为「4，12」，对应rank=2的签名文档第0列的文档就是「0，4，8，12」。
不同row rank
因此row rank更高的签名文件会增加row rank低的签名的bit密度。row rank为0（就是没有block）的签名就会转化成为多个row rank大于0签名文件。
不同row rank
现在假设有一query，分别对应不同的row rank签名文件匹配了对应的行（就是在不同的row rank签名文件当中，拿query的部分term来做匹配），如上图所示，那么最终的结果应当是这三行求交的结果。可是不同row rank的行长均不同，那么如何进行求交呢？答案是针对row rank高的行进行循环填充，生成它跟row rank 0等价的对应结果，然后再求交，如下图所示：
查询方式
4.2 Frequency Conscious Signatures
BitFunnel的另一个工作在于bloom filter本身。众所周知，在bloom filter中有一个常量k表示对term hash的次数，这个k对于任意term都是不变的。在实际中，不同的term词频是不一样的，要达到相同的false positive率，低频词相比高频词需要更高的k值。BitFunnel的做法是引入weighted bloom filter[3]来针对term分配不同的hash次数，从而起到节约内存的效果。
4.3 Shareding by Document Length
第三个设计在于分布式，同样由于bloom filter的因素，文档长短不一却用等长的签名文件表示，同样会引入更高的false positive，因此BitFunnel的做法是将长度相近的文档索引在同一个sharding。
5. 性能模型和最优化
5.1 预备知识
5.1.1 信号在Higher Rank Row
rank r与rank 0之间的关系：
image.png
5.1.2 噪音在Rank-0 Equivalent Row
在循环补位的时候会引入噪音。
image.png
image.png
5.1.3 相关噪音和不相关噪音
作者对Row Rank高位循环补位生成Rank-0 Equivalent Row产生的噪音分为了相关噪音和不相关噪音，相关噪音使用“C”表示，不相关噪音使用“U”表示，在查询中为0或者噪音，rank中为信号1的是相关噪音，其他事非相关噪音。
行的交集可以有效的消除不相关噪音，但是对相关噪音的影响不大。
5.2 信噪比
image.png
image.png
image.png
image.png
5.3 查询执行时间
image.png
5.4 内存消耗
image.png
5.5 选择Term配置
对于每一个term，给定信噪比、机器字读和内存消耗可以得出最优的行配置。
image.png
6. 实验评估
实验数据来源与实验条件
6.1 匹配时间 vs 四字节
image.png
查询时间与四字节数量有相关性，而且IDF值越大相关性越强。
6.2 Frequency Conscious Signatures和Higher Rank Rows表现
创新表现.png
Frequency Conscious Signatures技术相对于经典的布隆过滤器在对内存空间的优化同时还提升了速度，Higher Rank Rows主要表现在对速度的提升上。
6.3 与当前索引（倒排索引）技术对照
对比.png
从表里可以看出BitFunnel在所有数据集里都超过PEF，但是通过巨大代价带来——内存的消耗。数据集A中，使用了5倍的内存获得了1.62%的false positive。从5个数据集看出，MG4J性能低于PEF，他们使用相同的算法，只是MG4J使用Java实现。除了在数据集C中，MG4J性能都好于Lucene。
7. 结论
这篇论文重访了bit-sliced signatures并且描述了在当前商业搜索引擎中的使用，这个曾经使用倒排索引技术的搜索引擎。基于签名技术的方法会带来一些挑战，作者开发了一系列技术来减少内存空间的消耗和提高查询速度。更进一步的，作者提出了性能模型可以把系统的配置作为一个最优化问题来处理。
心得体会
我的体会
网友评论