搜索引擎中索引剪枝的研究

发布时间：2018-07-26 10:39

【摘要】：搜索引擎作为人们获取网络信息的主要入口，正在被越来越多的人使用。不断增长的网页数量和查询请求量使得搜索引擎面临着巨大的性能挑战。通常，搜索引擎每秒需要在数百亿的网页数据上处理成千上万的查询。因此，，如何高效地处理查询一直是搜索引擎和信息检索领域中重要的研究问题。本文从索引剪枝的角度出发来研究提升查询处理效率的方法。索引剪枝通常分为静态索引剪枝和动态索引剪枝的方法。静态索引剪枝方法主要用在索引构建阶段。它在索引构建时，去除索引中一些对查询不重要的信息来缩短倒排链长度，减小倒排索引的大小，从而提升查询的速度。动态索引剪枝的方法主要用在查询的处理阶段。它在查询的处理时，通过使用相应的索引辅助结构来跳过一些对查询不重要的文档来提升查询的处理速度。本文分别从静态索引剪枝和动态索引剪枝两方面来研究提升查询处理的方法，并提出了一些新的索引结构和算法来支持高效的查询处理。本文的工作、创新性和主要贡献主要体现在以下几个方面： 1.本文提出了一种基本网页结构和重要度的静态索引剪枝方法。在这种剪枝方法中，它一方面利用网页的结构来区别对待在不同结构中信息的重要程度，优先保留重要结构中的信息。另一方面利用网页与网页之间的重要度不同，对重要度高的网页保留更多比例的信息。通过在GOV2数据集上的相关实验，我们发现网页结构和重要度信息对文档的剪枝都有非常大的帮助。结合这两种信息的静态索引剪枝方法在去除80%的倒排项时，P@10指标与使用完整索引的效果相当，存储开销减小了73%，查询处理的速度提升了2倍。 2.本文提出了一种基于块最大索引的动态索引剪枝算法的处理框架。在此框架下，本文提出了3个新的动态索引剪枝算法，分别为Block-MaxMaxScore (BMM)， Local Block-Max WAND (LBMW)和Local Block-MaxMaxScore (LBMM)。在这个框架下查询处理主要分为三步：1).选择候选文档。本文提出的算法利用块局部最大分数而不是词的全局最大分数来选择候选文档，大大减少了选择候选文档的数量。2).过滤文档。利用文档所在块最大分数来过滤候选文档。本文提出一种更高效的过滤方法，它能充分的利用查询处理局部性，提升过滤的效率。3).候选文档打分。本文提出的算法利用块最大分数来动态估算文档分数上限，从而可以尽快的结束对不重要的候选文档的打分。实验表明，新提出剪枝算法在查询处理速度上比已有的算法都有明显的提升，它比经典的剪枝方法快近1倍。 3.本文提出了两种在块最大索引中存储文档静态分数与词相关性分数的方法。使得动态索引剪枝算法的打分函数在包含文档静态分数时也能对查询进行高效的剪枝。一种方法是对每个块分别存储块中最大的词相关性分数和文档静态分数；另一种方法是先把词相关性分数与文档静态分数合并，然后存储块中最大合并分数。第二种方法相对于第一种方法能更加精确地估算候选文档的分数，但它存在低估候选文档分数的情况。本文分析了产生文档分数低估的原因并给出了相应的解决方法。同时，本文还讨论了在不同文档重排序下对动态索引剪枝算法的影响。实验表明在打分公式中文档静态分数比例较小时，按URL序重排序的索引查询处理的速度比较快。当文档静态分数的比重增加时，则按文档静态分数序排序的索引的查询处理更有优势。 4.本文提出一种在区间最大索引中最优化区间划分的方法，并在这种区间划分的方式下，提出了4种动态索引剪枝算法：Space-Max WAND (SMW)，Space-Max MaxScore (SMM)，Space-Max AND (SMA)和Space Max AND withCheck (SMAC)。这种最优化区间划分的方法结合了文档分数估算误差和区间自身的处理开销等因素。它能在同等条件下对索引中的每个倒排链划分出最优的区间。利用区间最大的分数，新提出剪枝算法能更加精确的估算出候选文档的分数，减少找到候选文档的数量，同时对候选文档打分也能更早的结束。实验表明，这种基于最优化区间的方法的剪枝算法比根据倒排链长度来划分区间的方法处理查询的效率高。而基于区间最大索引的剪枝算法比基于块最大索引的剪枝算法效率高。 5.在上述的研究成果的基础上，重新设计并实现了天网搜索引擎。使得天网搜索引擎在索引量和查询处理的效率都有非常大的提升。
[Abstract]:The search engine is being used by more and more people as the main entrance to network information. The increasing number of web pages and query requests make the search engine face huge performance challenges. Often, search engines need to manage thousands of queries per second on the hundreds of billions of web pages. So how efficient Query processing has always been an important research issue in search engine and information retrieval field.
This paper studies the method of improving the efficiency of query processing from the angle of index pruning. Index pruning is usually divided into static index pruning and dynamic index pruning. The static index pruning method is mainly used in the index construction phase. When the index is built, some unimportant information in the index are removed to shorten the length of the inverted chain length. Degree, reducing the size of the inverted index to improve the speed of the query. The method of dynamic index pruning is mainly used in the processing phase of the query. In the processing of the query, it uses the corresponding index auxiliary structure to jump some queries that are not important to the query to improve the query rate. This article cuts and moves from the static index respectively. State index pruning in two aspects to study the method of improving query processing, and put forward some new index structure and algorithm to support efficient query processing.
The innovation and main contributions of this work are mainly reflected in the following aspects:
1. this paper presents a static index pruning method for basic web page structure and importance. In this pruning method, it uses the structure of the web page to distinguish the importance of information in different structures and to retain information in important structure. On the other hand, it is important to make use of the importance of the web page to the web. The web page structure and importance information are very helpful to the pruning of the document. The static index pruning method combined with these two kinds of information has the same effect as the use of a complete index when removing 80% inverted items with the two information. The cost is reduced by 73% and the query processing speed is increased by 2 times.
2. this paper presents a framework for the processing of dynamic index pruning algorithms based on block maximum index. Under this framework, 3 new dynamic index pruning algorithms are proposed, which are Block-MaxMaxScore (BMM), Local Block-Max WAND (LBMW) and Local Block-MaxMaxScore (LBMM). In this framework, the query processing is divided into three steps. 1). Select candidate documents. The proposed algorithm uses a local maximum fraction of the block instead of the global maximum fraction of the word to select the candidate document, greatly reducing the number of selected candidate documents.2). Filter the document. Filter the candidate document using the maximum block score of the document. This paper proposes a more efficient filtering method, which can be fully used. Using the query processing locality to improve the efficiency of filtering.3). The candidate document is graded. The proposed algorithm uses the block maximum score to dynamically estimate the upper limit of the document fraction, so that the score of the unimportant candidate documents can be ended as soon as possible. The experiment shows that the new pruning algorithm is better than the existing algorithms in the query processing speed. Obviously, it is nearly 1 times faster than the classical pruning method.
3. this paper presents two methods to store the static fraction of the document and the correlation fraction of the word in the block maximum index. It makes the scoring function of the dynamic index pruning algorithm effectively prune the query when it contains the static fraction of the document. One method is to store the maximum word correlation score and the document static of each block respectively. The other method is to combine the word correlation fraction with the document static fraction first, and then store the maximum merge score in the block. The second method can estimate the score of the candidate document more accurately than the first method, but it underestimates the candidate document fraction. At the same time, this paper also discusses the influence of the dynamic index pruning algorithm under different reordering of the document. The experiment shows that the rate of the document static fraction in the scoring formula is small, and the speed of the index query processing according to the URL order reordering is faster. Query processing with index sorting is more advantageous.
4. this paper presents a method for the optimal interval division in the interval maximum index. In this way, 4 dynamic index pruning algorithms are proposed: Space-Max WAND (SMW), Space-Max MaxScore (SMM), Space-Max AND (SMA) and Space Max AND. The optimal interval of each inverted chain in the index can be divided under the same condition. Using the maximum fraction of the interval, the new pruning algorithm can estimate the score of the candidate document more accurately, reduce the number of candidate documents, and score the candidate documents at the same time. The experiment shows that the pruning algorithm based on the optimal interval method is more efficient than the method based on the inverted chain length to divide the interval, and the pruning algorithm based on the maximum index of the interval is more efficient than the pruning algorithm based on the largest index of the block.
5. on the basis of the above research results, the Skynet search engine is redesigned and implemented, which makes the search engine in the sky network greatly improve the efficiency of index and query processing.
【学位授予单位】：北京大学
【学位级别】：博士
【学位授予年份】：2013
【分类号】：TP391.3

【相似文献】