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

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

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

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

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

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

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

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

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