互聯(lián)網(wǎng)搜索系統(tǒng)中的高性能查詢(xún)問(wèn)題研究.pdf

1、隨著網(wǎng)絡(luò)技術(shù)的迅速發(fā)展和互聯(lián)網(wǎng)應(yīng)用的不斷普及，可以從互聯(lián)網(wǎng)上獲得的信息呈爆炸式增長(zhǎng)，互聯(lián)網(wǎng)已經(jīng)成為全球規(guī)模最大、使用最廣泛的信息庫(kù)。為了有效地從這些海量數(shù)據(jù)中檢索到需要的信息，互聯(lián)網(wǎng)搜索引擎是一種必不可少的技術(shù)手段?；ヂ?lián)網(wǎng)搜索技術(shù)已經(jīng)成為信息檢索領(lǐng)域的重要研究課題。
　　 由于海量的網(wǎng)頁(yè)數(shù)據(jù)和巨大的查詢(xún)需求，搜索引擎的效率是影響信息獲取的關(guān)鍵問(wèn)題。因此，本文主要研究提高互聯(lián)網(wǎng)搜索效率的方法，并重點(diǎn)研究適用于大規(guī)模互聯(lián)網(wǎng)搜索的To

2、pK處理策略。TopK處理指使用各種優(yōu)化手段、以最小的代價(jià)從海量文本信息中獲得正確的前K個(gè)結(jié)果。能否實(shí)現(xiàn)高效的TopK算法，對(duì)互聯(lián)網(wǎng)搜索的性能至關(guān)重要。本文的主要貢獻(xiàn)包括以下幾個(gè)方面：
　　 1.本文提出了一種利用網(wǎng)頁(yè)結(jié)構(gòu)化數(shù)據(jù)特征的倒排索引結(jié)構(gòu)，并且提出了利用這種索引結(jié)構(gòu)的高效TopK處理策略。在通用網(wǎng)頁(yè)搜索中，當(dāng)相關(guān)排序函數(shù)考慮Term Proximity等多種因素的情況下，所提方法能明顯提高TopK處理的性能。本文還探討了

3、如何利用Term Proximity探測(cè)算法來(lái)進(jìn)一步避免不必要的Term Proximity分?jǐn)?shù)計(jì)算。在TREC數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文中提出的算法不僅適用于線(xiàn)性組合的排序函數(shù)，對(duì)非線(xiàn)性的排序函數(shù)也取得了明顯的效果，而且對(duì)于近似TopK處理問(wèn)題也獲得了預(yù)期效果。和傳統(tǒng)的索引方法相比，創(chuàng)建基于網(wǎng)頁(yè)結(jié)構(gòu)化數(shù)據(jù)特征的倒排索只增加很小的額外復(fù)雜度，而且沒(méi)有增加存儲(chǔ)空間消耗。因此，這種索引結(jié)構(gòu)完全符合大規(guī)模搜索引擎的需要。大量的實(shí)驗(yàn)結(jié)果證明本

4、文提出的索引結(jié)構(gòu)和算法是有效的。
　　 2.本文提出了一種通過(guò)對(duì)詞組建立輔助索引來(lái)提高TopK處理性能的策略?？紤]到傳統(tǒng)信息檢索能利用詞組索引來(lái)實(shí)現(xiàn)高效的詞組查詢(xún)處理，本文總結(jié)了Term Proximity函數(shù)和詞組的密切關(guān)系，提出對(duì)詞組建立輔助索引來(lái)降低對(duì)Term Proximity分?jǐn)?shù)上限的估計(jì)。這樣在對(duì)倒排索引進(jìn)行TopK處理時(shí)能夠提前滿(mǎn)足停止條件，或者節(jié)約不必要的Term Proximity分?jǐn)?shù)計(jì)算，從而提高了通用網(wǎng)頁(yè)搜

5、索中TopK處理的性能。同時(shí)本文還研究了詞組和詞頻分布的特點(diǎn)，提出只對(duì)最有必要的一部分詞組建立輔助索引，盡可能地減少詞組索引所占空間的開(kāi)銷(xiāo)。本文提出三種不同格式的精簡(jiǎn)詞組索引，并且比較它們的性能和空間效率，同時(shí)還研究了利用精簡(jiǎn)詞組索引幫助基于網(wǎng)頁(yè)結(jié)構(gòu)的倒排索引獲得更高的TopK處理性能的可能性。
　　 3.針對(duì)面向?qū)ο蟮乃阉飨到y(tǒng)，本文研究了對(duì)象聚合映射的TopK處理問(wèn)題，提出了一個(gè)高效的TopK處理框架。對(duì)象聚合映射指的是利用一

6、種對(duì)象的倒排索引有效地檢索出另一種對(duì)象。傳統(tǒng)的做法是將對(duì)象聚合映射的TopK處理分成檢索和聚合兩部分，而且主要優(yōu)化其中的聚合部分。和傳統(tǒng)方法不同，本文把檢索和聚合兩部分當(dāng)作一個(gè)整體來(lái)考慮，提出了三種TopK處理的優(yōu)化準(zhǔn)則，并且利用多種類(lèi)型對(duì)象的特征，建立了一種混合的倒排索引結(jié)構(gòu)，獲得了實(shí)質(zhì)意義上的TopK性能提升。
　　 綜上，本文提出了一系列針對(duì)互聯(lián)網(wǎng)信息檢索系統(tǒng)的TopK算法，通過(guò)在實(shí)際的大規(guī)模互聯(lián)網(wǎng)數(shù)據(jù)集上進(jìn)行的各種實(shí)驗(yàn)，