【摘要】：目前搜索引擎系統(tǒng)所處理的網頁數(shù)據(jù)量、用戶的查詢數(shù)量都在與日俱增，如何能高效地完成用戶查詢是最近幾年，無論是工業(yè)界還是學術界都在著力解決的問題，本文便是應上述需求而展開研究的。具體來說，本文探討了索引表求交算法和提前停止技術，我們還嘗試采用新一代的圖形顯卡技術來提升查詢處理的效率。具體工作包括以下幾方面： 第一，本文首先系統(tǒng)地回顧了目前的索引表求交算法，并采用真實搜索引擎的查詢集在GOV和GOV2數(shù)據(jù)集上對各種求交算法和搜索策略進行測試和概要分析，評價各種因素對求交算法性能的影響，并相應提出優(yōu)化方法。前人對求交和搜索算法的分析和評價主要關注比較次數(shù)對運行時間的影響，本文嘗試分析更接近系統(tǒng)架構層面的分支預測失敗次數(shù)和緩存失效次數(shù)對求交和搜索算法性能的重要影響。作者發(fā)現(xiàn)，基于SvS求交模型并使用哈希分段策略的算法性能最佳，盡管該算法的比較次數(shù)并不是最少的，但是在付出少量額外存儲空間的前提下，運行過程中的緩存失效和分支預測失敗數(shù)相對較低，從而達到了最佳的性能。本文還討論了文檔重排序對于求交算法性能的影響，大部分求交算法在按照URL排序的索引上的性能優(yōu)于文檔隨機編號的索引，且緩存失效數(shù)和分支預測失敗數(shù)更少。另外，通過表長的相對比值來分析求交算法中各種搜索策略的性能，，本文設計了一種啟發(fā)式的調度策略來提升求交算法的性能，實驗結果表明這種啟發(fā)式混合調度策略可以顯著提升索引表求交算法的性能。 第二，目前圖形顯卡（GPU）由于擁有強大的并行計算能力，已經越來越多地應用在各種科學計算的任務中。本文探討了利用GPU加速搜索引擎中的索引表求交算法以及后續(xù)的文檔分數(shù)計算、排序等步驟，實驗表明本文提出的算法可以大幅度提升查詢處理的吞吐率。具體來說，本文針對搜索引擎中可能存在的高查詢負載的交互式查詢或者非交互式查詢，提出了CPU-GPU協(xié)同工作模型來加速搜索引擎中的索引表求交運算。當系統(tǒng)處于低負載的時候，CPU還遠沒有達到負載上限時，查詢處理的響應時間是首先需要考慮的因素，每當新的查詢進入系統(tǒng)時，可以采用CPU或者GPU求交算法對查詢進行處理。而當系統(tǒng)處于高查詢負載或需要處理非交互式查詢時，則采用同步模式，其中若干查詢首先在CPU端組成批次，再發(fā)送到GPU上進行處理�；谏鲜瞿Ｐ停谔幚砀哓撦d查詢或者非交互查詢的情況下，利用GPU的大規(guī)模并行處理能力，查詢處理的吞吐率可以大幅增加。本文則提出并實現(xiàn)了這種批次求交的框架。在這個框架中，求交部分中的搜索算法是性能瓶頸，因此本文著重討論搜索算法的各種優(yōu)化策略。具體來說，在本文提出的GPU表求交算法中，當某兩個索引表1和2進行求交操作時（|1|≤|2|），對于1的每一個元素，GPU的每一個線程執(zhí)行某種搜索策略在2中進行搜索，以發(fā)現(xiàn)交集元素。其中最簡單的搜索策略為二分搜索，本文以該算法作為基準，提出了線性回歸搜索、哈希分段搜索和基于Bloom Filter的GPU求交算法。實驗結果顯示，本文提出幾種策略可以顯著提升GPU求交算法的性能，尤其是哈希分段算法的性能提升最為明顯。同時，本文還討論了索引重排對于GPU求交算法性能的影響。除此之外，本文還研究了如何在GPU求交算法的基礎上對文檔計算分數(shù)并排序，提出了一種適合GPU批次算法的文檔排序方法。 第三，本文還討論了求交運算后進一步優(yōu)化查詢處理，即利用提前停止技術優(yōu)化文檔排序工作。提前停止的基本思想是無需掃描完全部索引表，即可將與用戶查詢相關度分數(shù)最高的前k名文檔求出。針對于僅僅依賴全局信息排序的索引結構，很難獲得很好的提前停止效果的問題，本文提出了新的方法來重新組織索引結構，獲得了顯著的性能提升。具體來說，本文首先對提前停止效果和靜態(tài)排名分數(shù)、詞頻分數(shù)的分布之間的關系進行理論分析。本文發(fā)現(xiàn)只要詞頻分數(shù)是均勻分布的，提前停止的效果會非常好。然而，真實的詞頻分數(shù)是不服從均勻分布的，即某些分數(shù)的值的概率會高于其它分數(shù)值。而上述傾斜的分布正是導致全局排名方法提前停止效率較差的原因。本文提出了新的算法來依據(jù)某些額外的信息來重新安排倒排索引中文檔的組織方式。具體地，本文提出了利用文檔詞頻分數(shù)上界（UBIR）與靜態(tài)排名分數(shù)結合后的分數(shù)作為排序的標準重新組織索引結構，以提升查詢處理中提前停止的效果。通過這種方法，在進行查詢處理時，文檔詞頻數(shù)的估計值可以顯著地降低，從而可以更快地滿足提前停止的條件。本文還提出了其它幾種的基于全局信息對索引進行排序的方法。通過在GOV和GOV2數(shù)據(jù)集上比較本文提出的各種算法，并且與現(xiàn)有的全局排名的方法進行比較，結果顯示，本文的方法可以有效地提升查詢處理的效率。
[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

【相似文獻】

相關期刊論文 前10條

1 那罡;;移動搜索的“簡單”邏輯[J];中國計算機用戶;2006年26期

2 劉興波;;數(shù)據(jù)挖掘在搜索引擎中的應用[J];遼寧省交通高等�？茖W校學報;2008年03期

3 謝紅俠;惠正運;;一種面向文檔的XML的索引查詢方法[J];微機發(fā)展;2005年12期

4 許洪超;袁培燕;;智能搜索引擎系統(tǒng)的建模分析[J];福建電腦;2009年08期

5 陸小麗;何加銘;;基于Map/Reduce的索引數(shù)據(jù)云存儲模型研究[J];寧波大學學報(理工版);2011年03期

6 王路芳;張虎;;一種面向搜索引擎的基于集合模型的搜索算法[J];山西農業(yè)大學學報(自然科學版);2009年06期

7 盧秉亮;朱健;張磊;曹一鵬;;Internet搜索引擎索引數(shù)據(jù)庫的設計與實現(xiàn)[J];微處理機;2006年03期

8 吳啟明;;基于XML的搜索引擎[J];中國新技術新產品;2008年12期

9 張繼剛;搜索引擎使用技巧[J];網絡與信息;1999年09期

10 ;關鍵詞搜索[J];每周電腦報;2000年38期

相關會議論文 前10條

1 彭軻;廖聞劍;;淺析搜索引擎[A];中國通信學會第五屆學術年會論文集[C];2008年

2 李丹;;如何利用搜索引擎查找中醫(yī)藥信息[A];中國中醫(yī)藥信息研究會第二屆理事大會暨學術交流會議論文匯編[C];2003年

3 鄧長壽;郭景峰;楊焱林;鄧安遠;;下一代Web搜索引擎初探[A];第十八屆全國數(shù)據(jù)庫學術會議論文集（研究報告篇）[C];2001年

4 維尼拉·木沙江;吐爾洪·吾司曼;;維、哈、柯文搜索引擎中網頁爬行器的設計與實現(xiàn)[A];少數(shù)民族青年自然語言處理技術研究與進展——第三屆全國少數(shù)民族青年自然語言信息處理、第二屆全國多語言知識庫建設聯(lián)合學術研討會論文集[C];2010年

5 何璐;李晉宏;;基于XML的大容量搜索引擎技術探討[A];2006北京地區(qū)高校研究生學術交流會——通信與信息技術會議論文集（下）[C];2006年

6 湯薇;曾艷;;構建校園網搜索引擎必要性分析[A];廣西計算機學會2008年年會論文集[C];2008年

7 張維華;王國仁;于戈;鄭懷遠;;面向對象數(shù)據(jù)庫系統(tǒng)中索引的建立與維護[A];第十七屆全國數(shù)據(jù)庫學術會議論文集（研究報告篇）[C];2000年

8 姚樹宇;趙少東;;一種使用分布式技術的搜索引擎[A];2005年全國開放式分布與并行計算學術會議論文集[C];2005年

9 倪俊峰;;基于黃頁搜索引擎的關鍵字排名廣告系統(tǒng)的設計與實現(xiàn)[A];2005年中國索引學會年會暨學術研討會論文集[C];2005年

10 張怡;查貴庭;;SEO在信息服務中的應用研究[A];2010年中國索引學會年會暨學術研討會論文集[C];2010年

相關重要報紙文章 前10條

1 章森 王偉;搜索引擎的工作機制[N];計算機世界;2006年

2 李一鑫;搜索排名的紅與黑[N];財經時報;2007年

3 周文林;搜狗3.0能否撼動搜索市場[N];經濟參考報;2007年

4 惠正一;比爾·蓋茨:微軟不怕Google[N];第一財經日報;2005年

5 賽迪顧問股份有限公司互聯(lián)網與電子商務咨詢中心 常燕杰;搜索，還是門戶[N];中國計算機報;2005年

6 陳珊;浙江移動推出手機搜索引擎服務[N];人民郵電;2005年

7 趙法忠;搜索引擎還需悠著點[N];中國經營報;2005年

8 金朝力;搜索引擎火拼搜索質量[N];北京商報;2006年

9 本報記者　 趙曉輝 孟昭麗;搜索引擎駛入“避風港”[N];中國證券報;2006年

10 孫t;搜索引擎驚喜侵權官司止于“避風港”？[N];第一財經日報;2006年

相關博士學位論文 前10條

1 張帆;搜索引擎中索引表求交和提前停止技術優(yōu)化研究[D];南開大學;2012年

2 陳旭毅;基于索引云的企業(yè)搜索引擎實現(xiàn)研究[D];武漢大學;2011年

3 劉佐達;分布協(xié)作式搜索引擎模型及算法研究[D];清華大學;2011年

4 岑榮偉;基于用戶行為分析的搜索引擎評價研究[D];清華大學;2010年

5 李群;主題搜索引擎聚類算法的研究[D];北京林業(yè)大學;2011年

6 蘇君華;面向搜索引擎的技術接受模型研究[D];南京大學;2011年

7 郭眈;中文互聯(lián)網視頻搜索引擎系統(tǒng)策略研究[D];北京交通大學;2012年

8 王昤璞;基于用戶體驗的互聯(lián)網搜索引擎醫(yī)學信息檢索可用性評估研究[D];吉林大學;2010年

9 李莎莎;面向搜索引擎的自然語言處理關鍵技術研究[D];國防科學技術大學;2011年

10 白玉琪;空間信息搜索引擎研究[D];中國科學院研究生院（遙感應用研究所）;2003年

相關碩士學位論文 前10條

1 張蕾;基于Lucene的電子檔案檢索系統(tǒng)的設計與實現(xiàn)[D];西安電子科技大學;2010年

2 李浩;分布式教育網信息檢索系統(tǒng)的研究和實現(xiàn)[D];華南理工大學;2010年

3 張朝斌;企業(yè)級搜索引擎的優(yōu)化設計與實現(xiàn)[D];華南理工大學;2010年

4 尉建興;基于Lucene搜索引擎的研究與應用[D];太原理工大學;2011年

5 張彬;基于lucene的搜索引擎[D];上海師范大學;2010年

6 徐財應;基于Lucene的搜索引擎技術的研究與改進[D];長春理工大學;2010年

7 陳艷斐;基于用戶興趣模型的校園網搜索引擎設計與應用[D];云南大學;2010年

8 劉志偉;數(shù)學搜索引擎研究[D];蘭州大學;2011年

9 孫華昱;Lucene在醫(yī)學影像資源檢索平臺中的應用[D];沈陽工業(yè)大學;2011年

10 薛云;Internet上元搜索引擎的研究與設計[D];太原理工大學;2003年

本文編號：2404556