搜索引擎中索引表求交和提前停止技术优化研究

发布时间：2019-01-08 11:48

【摘要】：目前搜索引擎系统所处理的网页数据量、用户的查询数量都在与日俱增，如何能高效地完成用户查询是最近几年，无论是工业界还是学术界都在着力解决的问题，本文便是应上述需求而展开研究的。具体来说，本文探讨了索引表求交算法和提前停止技术，我们还尝试采用新一代的图形显卡技术来提升查询处理的效率。具体工作包括以下几方面：第一，本文首先系统地回顾了目前的索引表求交算法，并采用真实搜索引擎的查询集在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数据集上比较本文提出的各种算法，并且与现有的全局排名的方法进行比较，结果显示，本文的方法可以有效地提升查询处理的效率。
[Abstract]:At present, the number of web pages processed by the search engine system is increasing, and how to efficiently complete the user's query is the most recent years, whether industry or academia is working hard to solve, this paper is to study the above requirements. In particular, this paper discusses the index table intersection algorithm and the early stop technique, and we also try to improve the efficiency of query processing by using a new generation of graphic graphics card technology. The specific work includes the following aspects: First, this paper first systematically reviews the current index table intersection algorithm, and uses the query set of the real search engine to test and outline the various intersection algorithms and search strategies on the GOV and GOV2 data sets. The influence of various factors on the performance of the algorithm is evaluated, and the optimization method is put forward accordingly. In this paper, we try to analyze the influence of the number of branch prediction failures and the number of cache failures on the performance of the search algorithm and the search algorithm. In response, the author has found that the algorithm performance of the model based on SvS and using the hashing strategy is the best, although the number of the comparisons of the algorithm is not the least, the cache failure and the number of the branch prediction failures in the running process are relatively low on the premise of a small amount of extra storage space. low, thus achieving the best This paper also discusses the effect of re-ordering of documents on the performance of the algorithm. Most of the algorithms are better than the index of the random number of the document in the index ordered by the URL, and the number of cache failures and the number of branch prediction failures are more In addition, the performance of various search strategies in the intersection algorithm is analyzed by the relative ratio of the table length. In this paper, a heuristic scheduling strategy is designed to improve the performance of the algorithm. The experimental results show that this heuristic hybrid scheduling strategy can significantly improve the performance of the algorithm. Second, the current graphics graphics card (GPU) has been used more and more in various scientific computing because of its powerful parallel computing capability In this paper, the paper discusses the steps of using the algorithm of the index table in the GPU to accelerate the search engine and the subsequent calculation and sorting of the documents. The experiments show that the proposed algorithm can greatly improve the query processing. In this paper, an interactive query or non-interactive query of the high query load that may exist in the search engine is presented, and the CPU-GPU cooperative work model is proposed to speed up the index table in the search engine. When the system is in a low load, the response time of the query processing is the first to be considered when the system is in the low load, and each time the new query enters the system, the CPU or the GPU can be used to ask the algorithm to query the query. Line processing. When the system is in a high query load or a non-interactive query needs to be processed, a synchronization pattern is used, in which a number of queries first constitute a batch at the CPU end and then sent to the GPU. line processing. Based on the model, in the case of processing a high-load query or a non-interactive query, the throughput rate of the query processing can be large with the large-scale parallel processing capability of the GPU. In this paper, this paper presents and implements this batch. In this framework, the search algorithm in the intersection is the performance bottleneck, so this paper focuses on the various advantages of the search algorithm. Specifically, in the GPU table intersection algorithm proposed herein, when one of the two index tables 1 and 2 performs an intersection operation (| 1 | 1 | 2 |), for each element of 1, each thread of the GPU executes a search strategy to search in 2 to find the intersection The simplest search strategy is a binary search. In this paper, based on the algorithm, a linear regression search, a hash-segment search, and a Bloom Filter-based GPU are proposed. The experimental results show that several strategies can improve the performance of the algorithm, especially the performance of the hash segmentation algorithm. This paper also discusses the performance of the index rearrangement for GPU. In addition, the paper also studies how to compute the score of the document on the basis of the GPU's intersection algorithm, and put forward a kind of document bank suitable for GPU batch algorithm. The third, this paper also discusses the further optimization of query processing after the intersection operation, that is, using the advance stop technique to optimize the text. File sorting. The basic idea to stop in advance is that you can query the top k with the highest correlation score with the user without the need to scan the full index table. In this paper, a new method is proposed to re-organize the index structure. In particular, in this paper, the relationship between the early stop effect and the static ranking score and the word frequency score is first In this paper, we find that as long as the word frequency score is uniformly distributed, the effect of early stop The fruit will be very good. However, the true word frequency score is not subject to uniform distribution, that is, the probability of certain scores will be higher other fractional values. The above-described skew distribution is the leading end of the global ranking approach This paper proposes a new algorithm to rearrange the documents in the inverted index according to some extra information. In this paper, the index structure of the index is re-organized by using the score of the upper bound (UBIR) and the static ranking score in the document, so as to advance the advance in the query processing. By this method, when the query processing is performed, the estimated value of the frequency of the document word can be significantly reduced, so that the advance can be more quickly satisfied. In this paper, several other global information-based indexes are also put forward. By comparing the various algorithms proposed in this paper on the GOV and GOV2 data sets, and compared with the existing global ranking method, the results show that the method can effectively improve the query.
【学位授予单位】：南开大学
【学位级别】：博士
【学位授予年份】：2012
【分类号】：TP391.3

【相似文献】