圖形處理器對倒排索引求交運(yùn)算的優(yōu)化.pdf

1、大型搜索引擎系統(tǒng)每秒鐘都在響應(yīng)著大量的用戶請求。這些查詢請求希望從上百億張網(wǎng)頁中檢索出最相關(guān)的網(wǎng)頁集合。隨著互聯(lián)網(wǎng)業(yè)務(wù)的迅猛發(fā)展，搜索引擎系統(tǒng)檢索的信息量和承擔(dān)的計算負(fù)載正以指數(shù)增長速度膨脹。為了快速完成這些沉重的任務(wù)壓力，我們利用圖形處理器(Graphics Processing Units)來完成部分計算任務(wù)。在本文中，我們探討了幾種新的算法來加速搜索引擎中的一個重要且頻繁的操作：倒排索引求交。
　　 本文的主要工作包括：<

2、br>　　 1.為了充分發(fā)揮GPU的計算潛力，本文設(shè)計了批次處理模式。在批次模式下，若干個查詢被綁定為一個批次發(fā)送到GPU上進(jìn)行并行處理，以此取得較高的系統(tǒng)吞吐率。本文設(shè)計了查詢-線程塊并行策略(query-partition)來實現(xiàn)這個批次模型。為了改善負(fù)載均衡的情況，我們設(shè)計了docID-線程并行策略(query-parallel)。
　　 2.在系統(tǒng)負(fù)載較低的情況下，CPU或者GPU應(yīng)該立即處理當(dāng)前到達(dá)的查詢請求，以取得

3、最低的響應(yīng)時間。為此，本文設(shè)計了一個在線調(diào)度算法，用于將當(dāng)前到達(dá)的查詢派發(fā)到能夠最快完成任務(wù)的處理器上。
　　 3.本文將Bloom filter應(yīng)用到GPU倒排索引求交領(lǐng)域。雖然Bloom filter具有一定的誤稱率，但本文通過選擇合適的哈希函數(shù)，將錯誤結(jié)果比例控制在很低的水平。實驗顯示，Bloom filter方法符合GPU的并行特征，能夠大幅度提升系統(tǒng)吞吐率。
　　 4.本文分析了倒排索引的數(shù)據(jù)分布特征，總結(jié)出了

4、大部分倒排索引都具備明顯線性形態(tài)的重要結(jié)論。這種線性性質(zhì)來源于搜索引擎抓取網(wǎng)頁和分配docID過程中的隨機(jī)性和不確定性。為了增強(qiáng)這種線性特征，我們設(shè)計了利用fisher-yates隨機(jī)算法進(jìn)行倒排索引重排的策略。在線性性質(zhì)明顯的數(shù)據(jù)集合上，一元線性回歸能夠取得較好的擬合效果。
　　 5.本文在倒排索引數(shù)據(jù)分布的基礎(chǔ)上，設(shè)計了線性回歸搜索算法。良好的線性性質(zhì)等價于docID在倒排索引中的較均勻分布。因此，本文設(shè)計了哈希分段搜索算法