论文部分内容阅读
大型搜索引擎系统每秒钟都在响应着大量的用户请求。这些查询请求希望从上百亿张网页中检索出最相关的网页集合。随着互联网业务的迅猛发展,搜索引擎系统检索的信息量和承担的计算负载正以指数增长速度膨胀。为了快速完成这些沉重的任务压力,我们利用图形处理器(Graphics Processing Units)来完成部分计算任务。在本文中,我们探讨了几种新的算法来加速搜索引擎中的一个重要且频繁的操作:倒排索引求交。
本文的主要工作包括:
1.为了充分发挥GPU的计算潜力,本文设计了批次处理模式。在批次模式下,若干个查询被绑定为一个批次发送到GPU上进行并行处理,以此取得较高的系统吞吐率。本文设计了查询-线程块并行策略(query-partition)来实现这个批次模型。为了改善负载均衡的情况,我们设计了docID-线程并行策略(query-parallel)。
2.在系统负载较低的情况下,CPU或者GPU应该立即处理当前到达的查询请求,以取得最低的响应时间。为此,本文设计了一个在线调度算法,用于将当前到达的查询派发到能够最快完成任务的处理器上。
3.本文将Bloom filter应用到GPU倒排索引求交领域。虽然Bloom filter具有一定的误称率,但本文通过选择合适的哈希函数,将错误结果比例控制在很低的水平。实验显示,Bloom filter方法符合GPU的并行特征,能够大幅度提升系统吞吐率。
4.本文分析了倒排索引的数据分布特征,总结出了大部分倒排索引都具备明显线性形态的重要结论。这种线性性质来源于搜索引擎抓取网页和分配docID过程中的随机性和不确定性。为了增强这种线性特征,我们设计了利用fisher-yates随机算法进行倒排索引重排的策略。在线性性质明显的数据集合上,一元线性回归能够取得较好的拟合效果。
5.本文在倒排索引数据分布的基础上,设计了线性回归搜索算法。良好的线性性质等价于docID在倒排索引中的较均匀分布。因此,本文设计了哈希分段搜索算法。实验显示,线性回归搜索和哈希分段搜索均能够实现可观的加速比。