论文部分内容阅读
目前搜索引擎系统所处理的网页数据量、用户的查询数量都在与日俱增,如何能高效地完成用户查询是最近几年,无论是工业界还是学术界都在着力解决的问题,本文便是应上述需求而展开研究的。具体来说,本文探讨了索引表求交算法和提前停止技术,我们还尝试采用新一代的图形显卡技术来提升查询处理的效率。具体工作包括以下几方面:第一,本文首先系统地回顾了目前的索引表求交算法,并采用真实搜索引擎的查询集在GOV和GOV2数据集上对各种求交算法和搜索策略进行测试和概要分析,评价各种因素对求交算法性能的影响,并相应提出优化方法。前人对求交和搜索算法的分析和评价主要关注比较次数对运行时间的影响,本文尝试分析更接近系统架构层面的分支预测失败次数和缓存失效次数对求交和搜索算法性能的重要影响。作者发现,基于SvS求交模型并使用哈希分段策略的算法性能最佳,尽管该算法的比较次数并不是最少的,但是在付出少量额外存储空间的前提下,运行过程中的缓存失效和分支预测失败数相对较低,从而达到了最佳的性能。本文还讨论了文档重排序对于求交算法性能的影响,大部分求交算法在按照URL排序的索引上的性能优于文档随机编号的索引,且缓存失效数和分支预测失败数更少。另外,通过表长的相对比值来分析求交算法中各种搜索策略的性能,本文设计了一种启发式的调度策略来提升求交算法的性能,实验结果表明这种启发式混合调度策略可以显著提升索引表求交算法的性能。第二,目前图形显卡(GPU)由于拥有强大的并行计算能力,已经越来越多地应用在各种科学计算的任务中。本文探讨了利用GPU加速搜索引擎中的索引表求交算法以及后续的文档分数计算、排序等步骤,实验表明本文提出的算法可以大幅度提升查询处理的吞吐率。具体来说,本文针对搜索引擎中可能存在的高查询负载的交互式查询或者非交互式查询,提出了CPU-GPU协同工作模型来加速搜索引擎中的索引表求交运算。当系统处于低负载的时候,CPU还远没有达到负载上限时,查询处理的响应时间是首先需要考虑的因素,每当新的查询进入系统时,可以采用CPU或者GPU求交算法对查询进行处理。而当系统处于高查询负载或需要处理非交互式查询时,则采用同步模式,其中若干查询首先在CPU端组成批次,再发送到GPU上进行处理。基于上述模型,在处理高负载查询或者非交互查询的情况下,利用GPU的大规模并行处理能力,查询处理的吞吐率可以大幅增加。本文则提出并实现了这种批次求交的框架。在这个框架中,求交部分中的搜索算法是性能瓶颈,因此本文着重讨论搜索算法的各种优化策略。具体来说,在本文提出的GPU表求交算法中,当某两个索引表1和2进行求交操作时(|1|≤|2|),对于1的每一个元素,GPU的每一个线程执行某种搜索策略在2中进行搜索,以发现交集元素。其中最简单的搜索策略为二分搜索,本文以该算法作为基准,提出了线性回归搜索、哈希分段搜索和基于Bloom Filter的GPU求交算法。实验结果显示,本文提出几种策略可以显著提升GPU求交算法的性能,尤其是哈希分段算法的性能提升最为明显。同时,本文还讨论了索引重排对于GPU求交算法性能的影响。除此之外,本文还研究了如何在GPU求交算法的基础上对文档计算分数并排序,提出了一种适合GPU批次算法的文档排序方法。第三,本文还讨论了求交运算后进一步优化查询处理,即利用提前停止技术优化文档排序工作。提前停止的基本思想是无需扫描完全部索引表,即可将与用户查询相关度分数最高的前k名文档求出。针对于仅仅依赖全局信息排序的索引结构,很难获得很好的提前停止效果的问题,本文提出了新的方法来重新组织索引结构,获得了显著的性能提升。具体来说,本文首先对提前停止效果和静态排名分数、词频分数的分布之间的关系进行理论分析。本文发现只要词频分数是均匀分布的,提前停止的效果会非常好。然而,真实的词频分数是不服从均匀分布的,即某些分数的值的概率会高于其它分数值。而上述倾斜的分布正是导致全局排名方法提前停止效率较差的原因。本文提出了新的算法来依据某些额外的信息来重新安排倒排索引中文档的组织方式。具体地,本文提出了利用文档词频分数上界(UBIR)与静态排名分数结合后的分数作为排序的标准重新组织索引结构,以提升查询处理中提前停止的效果。通过这种方法,在进行查询处理时,文档词频数的估计值可以显著地降低,从而可以更快地满足提前停止的条件。本文还提出了其它几种的基于全局信息对索引进行排序的方法。通过在GOV和GOV2数据集上比较本文提出的各种算法,并且与现有的全局排名的方法进行比较,结果显示,本文的方法可以有效地提升查询处理的效率。