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

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

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

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

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

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

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

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

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