搜索引擎中的索引壓縮和查詢問題研究.pdf

1、隨著互聯(lián)網(wǎng)技術的飛速發(fā)展和互聯(lián)網(wǎng)應用的不斷普及，互聯(lián)網(wǎng)資源成為當前規(guī)模最大、內(nèi)容最豐富、使用最廣泛的信息來源。為了有效地從這些海量數(shù)據(jù)中檢索到需要的信息，搜索引擎已經(jīng)成為向用戶提供快速資源定位的最好技術手段。然而，不斷增長的網(wǎng)頁規(guī)模和查詢請求使得搜索引擎面臨著巨大的性能挑戰(zhàn)。面對海量的網(wǎng)頁數(shù)據(jù)和巨大的查詢需求，如何高效地處理查詢請求成為搜索引擎領域中最重要的研究問題之一。在查詢性能上的任何提升都可以顯著地降低系統(tǒng)硬件資源的投入并提升用戶

2、的查詢體驗，從而為搜索引擎的良好運行提供堅實的基礎。因此，本文主要研究提高搜索引擎效率的方法，并重點從倒排索引壓縮和查詢兩方面技術結合的角度出發(fā)來解決制約搜索引擎系統(tǒng)性能的問題。本文的主要研究成果如下：
　　（1）為了提升搜索引擎系統(tǒng)索引數(shù)據(jù)的壓縮性能，本文研究了典型的Simple9索引壓縮算法。針對Simple9壓縮算法中存在的填充模式間可壓縮整數(shù)個數(shù)的稀疏問題，本文提出了密集填充技術（Dense Padding）來使一個32位

3、機器字能夠壓縮更多的整數(shù)，從而提升Simple9索引壓縮算法的壓縮率。當某一填充模式中異常值的相對位置大于下一個填充模式的可壓縮整數(shù)個數(shù)時，我們通過在被壓縮整數(shù)序列末尾插入整數(shù)0來構造滿足本填充模式的可壓縮整數(shù)序列。在解壓過程中，我們設計巧妙的算法來去除額外的整數(shù)0。此外，針對Simple9中可壓縮數(shù)字序列個數(shù)較少的導致的位操作過多問題，本文提出了分組 Simple9壓縮技術（GroupSimple9）來降低壓縮和解壓縮過程中的數(shù)據(jù)讀取

4、、分支判斷、移位和查找映射表等位操作，從而提升Simple9壓縮算法的壓縮和解壓速度。實驗結果表明，本文提出的分組Simple9和密集Simple9（DenseSimple9）壓縮算法能夠在壓縮率、壓縮和解壓三方面上均有明顯的性能提升。
　?。?）為了提升搜索引擎系統(tǒng)索引數(shù)據(jù)的查詢性能，本文研究了當前流行的MaxScore動態(tài)剪枝算法。由于當前MaxScore查詢算法是在必要表（Essential Lists）中進行選擇候選文檔，

5、非必要表（Non-essential Lists）的倒排項僅進行分數(shù)貢獻累加。MaxScore查詢算法對必要表的訪問是順序進行的，而僅僅對非必要表采用隨機訪問，這種情況下MaxScore查詢算法存在著嚴重的候選文檔失效問題。針對這一問題，本文首先實現(xiàn)了一種多層自索引結構（Hierarchical Self-index）來支持倒排鏈表的隨機訪問，然后提出對候選文檔最大可能分數(shù)進行雙向檢查，實現(xiàn)了必要表的快速跳躍訪問（Essential L

6、ists Skipping, ELS）。這樣實現(xiàn)必要表中候選文檔的預先檢測和隨機訪問，使得候選文檔的打分失效問題能夠盡早被發(fā)現(xiàn)，避免在將要失效的候選文檔上的一些無用的操作。實驗結果表明，本文提出的ELS-MaxScore查詢算法能夠大大提升top-k查詢性能，尤其在查詢長度小于4時能達到MaxScore近2倍的性能。
　?。?）通過之前的分析可以發(fā)現(xiàn)提升搜索引擎查詢性能的一個方法是，候選文檔的選擇應該主要集中在重要度較高的詞項對應

7、的倒排鏈表中。在分析WAND查詢算法問題和研究激進式MaxScore（Aggressive MaxScore）優(yōu)勢的基礎上，為了更好的利用詞項重要度這一重要特性，本文提出了最大重要度優(yōu)先（Largest Score First, LSF）查詢算法。LSF查詢算法使得具有較高重要度的查詢詞項所指向的倒排鏈表能夠優(yōu)先得到處理。分析表明，LSF查詢算法能夠解決當前（Document At A Time, DAAT）和（Term At A Ti

8、me, TAAT）兩種窮盡遍歷算法中存在的候選文檔隨機選擇和內(nèi)存消耗問題。為了進一步支持高效的動態(tài)剪枝算法，本文利用 LSF查詢的對于詞項重要度考慮的優(yōu)勢，提出了兩種精確的動態(tài)剪枝算法：基于 LSF的去除查詢詞項技術（Term Omitting，LSF_TO）和基于LSF的文檔部分打分技術（Partial Scoring，LSF_PS）?；赥REC GOV2上的實驗結果表明，本文提出的兩種基于LSF索引遍歷的動態(tài)剪枝算法能夠達到比基于