搜索引擎中索引表求交和提前停止技術(shù)優(yōu)化研究.pdf

1、目前搜索引擎系統(tǒng)所處理的網(wǎng)頁數(shù)據(jù)量、用戶的查詢數(shù)量都在與日俱增，如何能高效地完成用戶查詢是最近幾年，無論是工業(yè)界還是學(xué)術(shù)界都在著力解決的問題，本文便是應(yīng)上述需求而展開研究的。具體來說，本文探討了索引表求交算法和提前停止技術(shù)，我們還嘗試采用新一代的圖形顯卡技術(shù)來提升查詢處理的效率。具體工作包括以下幾方面:
　　 第一，本文首先系統(tǒng)地回顧了目前的索引表求交算法，并采用真實(shí)搜索引擎的查詢集在GOV和GOV2數(shù)據(jù)集上對(duì)各種求交算法和搜索

2、策略進(jìn)行測試和概要分析，評(píng)價(jià)各種因素對(duì)求交算法性能的影響，并相應(yīng)提出優(yōu)化方法。前人對(duì)求交和搜索算法的分析和評(píng)價(jià)主要關(guān)注比較次數(shù)對(duì)運(yùn)行時(shí)間的影響，本文嘗試分析更接近系統(tǒng)架構(gòu)層面的分支預(yù)測失敗次數(shù)和緩存失效次數(shù)對(duì)求交和搜索算法性能的重要影響。作者發(fā)現(xiàn)，基于SvS求交模型并使用哈希分段策略的算法性能最佳，盡管該算法的比較次數(shù)并不是最少的，但是在付出少量額外存儲(chǔ)空間的前提下，運(yùn)行過程中的緩存失效和分支預(yù)測失敗數(shù)相對(duì)較低，從而達(dá)到了最佳的性能。本

3、文還討論了文檔重排序?qū)τ谇蠼凰惴ㄐ阅艿挠绊?，大部分求交算法在按照URL排序的索引上的性能優(yōu)于文檔隨機(jī)編號(hào)的索引，且緩存失效數(shù)和分支預(yù)測失敗數(shù)更少。另外，通過表長的相對(duì)比值來分析求交算法中各種搜索策略的性能，本文設(shè)計(jì)了一種啟發(fā)式的調(diào)度策略來提升求交算法的性能，實(shí)驗(yàn)結(jié)果表明這種啟發(fā)式混合調(diào)度策略可以顯著提升索引表求交算法的性能。
　　 第二，目前圖形顯卡(GPU)由于擁有強(qiáng)大的并行計(jì)算能力，已經(jīng)越來越多地應(yīng)用在各種科學(xué)計(jì)算的任務(wù)中。

4、本文探討了利用GPU加速搜索引擎中的索引表求交算法以及后續(xù)的文檔分?jǐn)?shù)計(jì)算、排序等步驟，實(shí)驗(yàn)表明本文提出的算法可以大幅度提升查詢處理的吞吐率。具體來說，本文針對(duì)搜索引擎中可能存在的高查詢負(fù)載的交互式查詢或者非交互式查詢，提出了CPU-GPU協(xié)同工作模型來加速搜索引擎中的索引表求交運(yùn)算。當(dāng)系統(tǒng)處于低負(fù)載的時(shí)候，CPU還遠(yuǎn)沒有達(dá)到負(fù)載上限時(shí)，查詢處理的響應(yīng)時(shí)間是首先需要考慮的因素，每當(dāng)新的查詢進(jìn)入系統(tǒng)時(shí)，可以采用CPU或者GPU求交算法對(duì)查詢

5、進(jìn)行處理。而當(dāng)系統(tǒng)處于高查詢負(fù)載或需要處理非交互式查詢時(shí)，則采用同步模式，其中若干查詢首先在CPU端組成批次，再發(fā)送到GPU上進(jìn)行處理?；谏鲜瞿Ｐ?，在處理高負(fù)載查詢或者非交互查詢的情況下，利用GPU的大規(guī)模并行處理能力，查詢處理的吞吐率可以大幅增加。本文則提出并實(shí)現(xiàn)了這種批次求交的框架。在這個(gè)框架中，求交部分中的搜索算法是性能瓶頸，因此本文著重討論搜索算法的各種優(yōu)化策略。具體來說，在本文提出的GPU表求交算法中，當(dāng)某兩個(gè)索引表(e)1

6、和(e)2進(jìn)行求交操作時(shí)（|(e)1｜≤|(e)2|），對(duì)于(e)1的每一個(gè)元素，GPU的每一個(gè)線程執(zhí)行某種搜索策略在(e)2中進(jìn)行搜索，以發(fā)現(xiàn)交集元素。其中最簡單的搜索策略為二分搜索，本文以該算法作為基準(zhǔn)，提出了線性回歸搜索、哈希分段搜索和基于BloomFilter的GPU求交算法。實(shí)驗(yàn)結(jié)果顯示，本文提出幾種策略可以顯著提升GPU求交算法的性能，尤其是哈希分段算法的性能提升最為明顯。同時(shí)，本文還討論了索引重排對(duì)于GPU求交算法性能的影

7、響。除此之外，本文還研究了如何在GPU求交算法的基礎(chǔ)上對(duì)文檔計(jì)算分?jǐn)?shù)并排序，提出了一種適合GPU批次算法的文檔排序方法。
　　 第三，本文還討論了求交運(yùn)算后進(jìn)一步優(yōu)化查詢處理，即利用提前停止技術(shù)優(yōu)化文檔排序工作。提前停止的基本思想是無需掃描完全部索引表，即可將與用戶查詢相關(guān)度分?jǐn)?shù)最高的前(k)名文檔求出。針對(duì)于僅僅依賴全局信息排序的索引結(jié)構(gòu)，很難獲得很好的提前停止效果的問題，本文提出了新的方法來重新組織索引結(jié)構(gòu)，獲得了顯著的性能

8、提升。具體來說，本文首先對(duì)提前停止效果和靜態(tài)排名分?jǐn)?shù)、詞頻分?jǐn)?shù)的分布之間的關(guān)系進(jìn)行理論分析。本文發(fā)現(xiàn)只要詞頻分?jǐn)?shù)是均勻分布的，提前停止的效果會(huì)非常好。然而，真實(shí)的詞頻分?jǐn)?shù)是不服從均勻分布的，即某些分?jǐn)?shù)的值的概率會(huì)高于其它分?jǐn)?shù)值。而上述傾斜的分布正是導(dǎo)致全局排名方法提前停止效率較差的原因。本文提出了新的算法來依據(jù)某些額外的信息來重新安排倒排索引中文檔的組織方式。具體地，本文提出了利用文檔詞頻分?jǐn)?shù)上界(UBIR)與靜態(tài)排名分?jǐn)?shù)結(jié)合后的分?jǐn)?shù)作