馬宏遠(yuǎn),王斌

(1.中國科學(xué)院計(jì)算技術(shù)研究所,北京100190;2.中國科學(xué)院研究生院,北京100049)

1 引言

據(jù)中國互聯(lián)網(wǎng)絡(luò)信息中心(China Internet Network Information Center,CNNIC)研究報(bào)告顯示[1],截至2010年12月,中國網(wǎng)民達(dá)到4.57億,其中搜索引擎使用率達(dá)到81.9%,搜索引擎已經(jīng)成為人們獲取信息的主要工具。一方面,互聯(lián)網(wǎng)網(wǎng)民增多,搜索引擎工作負(fù)載變大;另一方面,互聯(lián)網(wǎng)網(wǎng)頁也逐年增多,其規(guī)模已經(jīng)達(dá)到600億,且仍以年增長率超過50%的速度快速膨脹,搜索引擎需要盡可能多地索引這些網(wǎng)頁以提供準(zhǔn)確和豐富的查詢結(jié)果。在如此海量信息中,高效獲取所需查詢對學(xué)術(shù)界和工業(yè)界提出挑戰(zhàn)。自21世紀(jì)初以來,隨著互聯(lián)網(wǎng)步入高速發(fā)展時(shí)期,一些搜索引擎檢索系統(tǒng)性能優(yōu)化方法先后被提出,主要有并行處理(Massively Par-allel Processing)、索引壓縮(Index Compression)、索引裁剪(Index Prune)、倒排表跳轉(zhuǎn)(List Skipping)、提早結(jié)束(Early Termination)等技術(shù)。除此之外,緩存技術(shù)(Caching)與預(yù)取技術(shù)(Prefetching)作為重要的系統(tǒng)性能優(yōu)化手段而被搜索引擎檢索系統(tǒng)廣泛采用和研究。

緩存是一種通過存放將來可能被請求的數(shù)據(jù)以提高數(shù)據(jù)訪問速度。被存放的數(shù)據(jù)可能是計(jì)算結(jié)果或者數(shù)據(jù)的副本。如果請求的數(shù)據(jù)在緩存中被查找到,就直接獲取該結(jié)果或者副本,否則,請求需要再次計(jì)算或者從其位置獲得該數(shù)據(jù)。如果更多的請求能夠被緩存所滿足,則意味著系統(tǒng)的整體效率會(huì)被提高。緩存被廣泛應(yīng)用于計(jì)算機(jī)系統(tǒng)及應(yīng)用軟件的各個(gè)層次,譬如CPU緩存、磁盤緩存、Web緩存。

在本文中,我們提出一種基于查詢特性的查詢結(jié)果緩存與預(yù)取的方法,該方法包括用來指導(dǎo)預(yù)取的查詢結(jié)果頁碼預(yù)測模型和基于查詢特性的分區(qū)緩存。在國內(nèi)某著名中文商業(yè)搜索引擎用戶查詢?nèi)罩旧向?yàn)證了我們提出方法的有效性。本文第2節(jié)分析搜索引擎查詢特性;第3節(jié)闡述基于查詢特性的查詢結(jié)果頁碼預(yù)測模型,給出全局和局部預(yù)測模型;第4節(jié)闡述基于查詢特性的查詢結(jié)果緩存與預(yù)取算法框架;第5節(jié)是實(shí)驗(yàn)結(jié)果及分析;第6節(jié)是本文結(jié)論及未來工作。

2 相關(guān)工作

查詢結(jié)果緩存是通過緩存已被用戶檢索過的查詢結(jié)果以避免再次對該結(jié)果進(jìn)行排名計(jì)算帶來的CPU和磁盤讀開銷。Markatos[2]首先對搜索引擎環(huán)境下,查詢結(jié)果緩存技術(shù)進(jìn)行研究,通過分析Excite用戶查詢?nèi)罩?顯示其工作負(fù)載具有時(shí)間局部性(Temporal Locality),比較動(dòng)態(tài)LRU緩存替換策略以及LRU策略的若干變種和靜態(tài)緩存策略的命中率,得出靜態(tài)緩存策略對小容量緩存有效,隨著容量增大,有效性降低。Xie[3]討論緩存位置的影響,分別討論客戶端緩存、代理服務(wù)器緩存和搜索引擎服務(wù)器緩存技術(shù)。Fagni[4]提出靜態(tài)、動(dòng)態(tài)混合的緩存策略,其將緩存分為靜態(tài)緩存和動(dòng)態(tài)緩存兩個(gè)部分。靜態(tài)緩存用于存放通過預(yù)先分析得到的流行查詢結(jié)果;動(dòng)態(tài)緩存用于存放其余的查詢結(jié)果。Baeze-Yates[5]從緩存接納策略角度提出了一種能有效識(shí)別不流行的查詢的緩存方法,可以阻止不必要的緩存內(nèi)容進(jìn)入緩存占用其他有價(jià)值的緩存內(nèi)容。Gan和Suel[6]提出基于查詢開銷的查詢結(jié)果緩存方法,考慮查詢頻率和開銷來對查詢結(jié)果給予不同權(quán)重。Ozcan[7]提出基于查詢穩(wěn)定度的查詢結(jié)果緩存方法,考慮查詢在一定時(shí)期內(nèi)的穩(wěn)定程度來選擇查詢結(jié)果。Skobeltsyn[8]提出一種結(jié)合索引裁剪技術(shù)的查詢結(jié)果緩存方法。查詢結(jié)果預(yù)取是通過預(yù)測Follow-up查詢[9],提前取得查詢結(jié)果。Lempel[9]根據(jù)查詢自身特性,建立Follow-up查詢頁碼分布,提出了一種基于該分布的查詢結(jié)果預(yù)取方法。Fagni[4]通過分析查詢請求頁碼對Follow-up查詢的影響,提出一種基于當(dāng)前請求查詢頁碼的自適應(yīng)查詢結(jié)果預(yù)取方法。對于Web緩存預(yù)取[10],主要是通過分析用戶訪問 URL順序來預(yù)測訪問路徑,以預(yù)取用戶數(shù)據(jù)。

3 搜索引擎查詢特性分析

用戶行為分析是系統(tǒng)優(yōu)化的重要基石,文獻(xiàn)[3,11-13]對搜索引擎的用戶行為進(jìn)行分析來開展相關(guān)工作。與以往分析工作不同,本文著重分析搜索引擎查詢特性。本文數(shù)據(jù)來自于國內(nèi)某著名中文商業(yè)搜索引擎從2006年9月1日到2006年10月31日的用戶查詢?nèi)罩?包括近3000多萬條用戶查詢和1億多條用戶點(diǎn)擊記錄。我們從該日志中提取了所有用戶對該搜索引擎發(fā)起的查詢請求,作為分析搜索引擎查詢結(jié)果頁瀏覽特性的基礎(chǔ)。

圖1 搜索引擎查詢特性

查詢,即查詢主題,是用戶對信息檢索需求的具體表達(dá),用戶提交查詢給搜索引擎。不同的查詢意圖對查詢結(jié)果瀏覽行為會(huì)產(chǎn)生重要影響,譬如用戶要搜索“新浪”,通常只瀏覽第一頁查詢結(jié)果就可以得到自己需要的信息。文獻(xiàn)[14]提出了一種查詢意圖分類方法,將查詢分為：(1)導(dǎo)航類;(2)信息類;(3)事務(wù)類。圖1(a)是在該搜索引擎用戶查詢?nèi)罩旧?統(tǒng)計(jì)用戶瀏覽的查詢結(jié)果頁數(shù),可以看出9%的查詢主題只瀏覽了一頁,這些主題大部分屬于導(dǎo)航類查詢?？梢?用戶瀏覽查詢結(jié)果頁數(shù)的分布具有顯著非均衡性。圖1(b)是在該搜索引擎用戶查詢?nèi)罩旧?統(tǒng)計(jì)用戶瀏覽查詢結(jié)果頁碼,可以看出頁碼范圍越靠前的訪問量遞減趨勢相比于相對靠后的頁碼范圍內(nèi)的訪問量遞減趨勢要明顯。

4 基于查詢特性的查詢結(jié)果頁碼預(yù)測模型

4.1 相關(guān)定義

我們將搜索引擎用戶集合定義為U,用戶提交查詢集合定義為Q,用戶提交搜索查詢主題集合定義為T,用戶提交搜索查詢頁碼集合定義為P,用戶查詢?nèi)罩究偛樵儣l數(shù)定義為N。那么,用戶查詢?nèi)罩究梢员硎緸椋?/p>

即用戶查詢?nèi)罩局械牡趇條查詢記錄為：在時(shí)刻τi,用戶ui向搜索引擎提交的查詢主題為ti,查詢頁碼為 pi。用戶每次提交查詢頁碼集合可以表示為：

給定主題t,該主題下的查詢頁碼集合表示為：

4.2 基于馬爾可夫鏈模型

從我們對該搜索引擎用戶查詢?nèi)罩窘y(tǒng)計(jì)表明,約96%的查詢請求訪問查詢結(jié)果頁碼順序是非逆序的(由于篇幅限制,未貼此結(jié)果)?；诖耸聦?shí),引入如下假設(shè)：用戶以頁碼的自然順序訪問查詢結(jié)果頁。我們使用基于馬爾可夫鏈的方法設(shè)計(jì)預(yù)測模型,狀態(tài)轉(zhuǎn)移概率如圖2所示,狀態(tài)“i”(1≤i≤n)表示用戶發(fā)起一個(gè)查詢主題t,請求頁碼為“i”;狀態(tài)“0”表示用戶發(fā)起一個(gè)查詢主題t后,不再對該主題產(chǎn)生頁碼請求。在任意時(shí)刻τj,當(dāng)前訪問頁號(hào) Xj和所有以前訪問頁號(hào)X1,X2,…,Xj-1的信息是已知的,所有將來的訪問頁號(hào)Xj+1僅依賴于現(xiàn)在的信息 Xj,而不依賴以往的信息 X1,X2,…,Xj-1,有：

那么,我們在模型設(shè)計(jì)過程中,需要獲得Pr(Xj+1=i+1|Xj=i)即狀態(tài)轉(zhuǎn)移圖中由狀態(tài)“i”轉(zhuǎn)移到狀態(tài)“i+1”的概率pi,i+1。

圖2 查詢請求頁碼狀態(tài)轉(zhuǎn)移圖

4.3 查詢結(jié)果頁碼預(yù)測模型

在第2節(jié)中,我們分析了國內(nèi)某中文商業(yè)搜索引擎的查詢特性,用戶瀏覽查詢結(jié)果頁數(shù)具有顯著非均衡性。我們采用4.1節(jié)提出的模型設(shè)計(jì)用戶瀏覽查詢結(jié)果頁碼預(yù)測模型,模型分為全局預(yù)測模型和部分預(yù)測模型。

1)全局預(yù)測模型

全局預(yù)測模型通過記錄用戶瀏覽查詢主題的統(tǒng)計(jì)信息進(jìn)行預(yù)測。根據(jù)Pt集合的歷史信息,將查詢主題t對于查詢結(jié)果頁碼i的訪問次數(shù)記作Countt[i],那么,采用如下定義：

即考慮所有查詢主題的查詢結(jié)果頁的分布。我們采用如下方法計(jì)算查詢結(jié)果頁碼訪問概率：

根據(jù)上面的定義,給定一個(gè)用戶對某個(gè)查詢主題t當(dāng)前訪問的查詢結(jié)果頁碼i,預(yù)測該用戶瀏覽該查詢主題的查詢結(jié)果頁碼集合Ωt,預(yù)測模型如下,其中用來調(diào)節(jié)預(yù)測效果：

全局預(yù)測模型認(rèn)為所有查詢主題都是平等的,每個(gè)查詢主題都是用該模型進(jìn)行預(yù)測,搜索引擎需要存儲(chǔ)所有查詢主題的查詢結(jié)果訪問信息。

2)部分預(yù)測模型

部分預(yù)測模型通過記錄用戶瀏覽的部分查詢主題的統(tǒng)計(jì)信息進(jìn)行預(yù)測。選取高頻查詢集合作為統(tǒng)計(jì)主體。根據(jù)Pt集合的歷史信息,將查詢主題t對于查詢結(jié)果頁碼i的訪問次數(shù)記作Countt[i],那么,采用如下定義：

即只考慮部分查詢主題 TSpec的查詢結(jié)果頁的分布。我們采用如下方法計(jì)算查詢結(jié)果頁碼訪問概率：

4.4 模型閥值選取方法

我們采用如下兩種方法來確定閥值：(1)設(shè)置固定閥值,采用固定值,需要預(yù)先設(shè)定,閥值與用戶瀏覽當(dāng)前查詢的查詢結(jié)果頁碼無關(guān);(2)動(dòng)態(tài)調(diào)整閥值,閥值與用戶瀏覽當(dāng)前查詢的查詢結(jié)果頁碼有關(guān)。

5 算法框架

在本文第4節(jié)中,我們給出基于查詢特性的查詢結(jié)果頁碼預(yù)測模型。本節(jié)將在此基礎(chǔ)上,給出基于查詢特性的緩存與預(yù)取算法框架,如算法1所示。對于部分預(yù)測模型,緩存系統(tǒng)分為兩個(gè)區(qū)間：查詢結(jié)果緩存區(qū)和查詢結(jié)果緩存區(qū)。當(dāng)搜索引擎收到用戶的某一查詢主題t時(shí),緩存系統(tǒng)應(yīng)該首先在t所屬的集合所對應(yīng)的查詢結(jié)果緩存區(qū)中查詢,以提高緩存檢索相關(guān)條目操作的效率。

算法1 基于用戶特性的查詢結(jié)果緩存與預(yù)取算法框架

算法1給出了基于查詢特性的查詢結(jié)果緩存與預(yù)取算法框架,我們在此給出算法時(shí)間復(fù)雜度和空間復(fù)雜度分析。第6行,在緩存中檢索該查詢請求的查詢結(jié)果,該操作依賴于緩存中信息條目的具體組織方式,通常,采用基于哈希的組織方式使該操作開銷為Ο(1)。第 11行,緩存條目更新,該操作依賴于所采用的緩存替換策略,如LRU策略的緩存替換時(shí)間復(fù)雜度為 Ο(1),記作Complexity(Replacement_policy)。第21行,預(yù)測查詢結(jié)果頁碼集合,由于此過程需要獲得該查詢相關(guān)的統(tǒng)計(jì)信息,其依賴于信息的具體組織,可以采用二維表的方式,查詢主題ID作為表的行項(xiàng),因此,該過程時(shí)間復(fù)雜度為Ο(1)。綜上分析,該算法的時(shí)間復(fù)雜度依賴于所使用緩存替換策略的時(shí)間復(fù)雜度,Complexity-(Replacement-policy)。算法的空間開銷來自于預(yù)測模型計(jì)算所需要的統(tǒng)計(jì)信息,通常,全局預(yù)測模型需要存儲(chǔ)所有查詢主題的統(tǒng)計(jì)信息,而部分預(yù)測模型只需要存儲(chǔ)查詢主題的統(tǒng)計(jì)信息。

6 實(shí)驗(yàn)與分析

6.1 數(shù)據(jù)集

本文實(shí)驗(yàn)數(shù)據(jù)集來自于國內(nèi)某著名中文商業(yè)搜索引擎從2006年9月1日到2006年10月31日的用戶查詢?nèi)罩尽＿x取前500萬條用戶查詢記錄預(yù)熱查詢結(jié)果緩存,剩下約2500萬條用戶查詢記錄作為查詢結(jié)果緩存的工作負(fù)載。

6.2 評(píng)價(jià)方法

搜索引擎緩存系統(tǒng)是提升系統(tǒng)整體性能的重要手段,緩存系統(tǒng)性能的優(yōu)劣對整體有著重要影響。通常,緩存是以命中率作為其衡量指標(biāo),由于緩存系統(tǒng)實(shí)際受到存儲(chǔ)容量的限制,需要考慮存儲(chǔ)容量因素,即當(dāng)緩存條目達(dá)到一定空間后需要以某種策略替換某些條目。為了分析存儲(chǔ)容量對緩存命中率的影響,我們采用工作集模型[15]離線計(jì)算該用戶查詢?nèi)罩镜睦碚摼彺婷新?。在該用戶查詢?nèi)罩镜牟樵冋埱筘?fù)載下,緩存容量和命中率的關(guān)系曲線如圖3所示。當(dāng)緩存容量大于0.025(實(shí)際緩存查詢結(jié)果條目占總查詢條目的百分比)時(shí),命中率變化趨勢趨于平緩。在實(shí)驗(yàn)中,我們近似選取5K、10K、20K、50K 、75K 、100K 、150K 、200K 、250K 條查詢結(jié) 果作為緩存容量來分析緩存性能。從圖中可以看出,查詢結(jié)果緩存命中率理論上界為58.44%(Normalized Size=1時(shí))。

圖3 工作集模型下的理論緩存命中率

離線策略通常是用作緩存替換算法的理論分析,需要預(yù)先知道當(dāng)前訪問時(shí)間以后的全部或者部分工作負(fù)載。預(yù)先知道工作負(fù)載是不現(xiàn)實(shí)的,因此,離線策略是不可能在實(shí)際系統(tǒng)中實(shí)現(xiàn)的。在理論分析中,根據(jù)預(yù)先知道工作負(fù)載的多少可以將離線替換策略分為全局最佳替換策略(Global-OPT)[16]和局部最佳替換策略(Local-OPT)[17]。由于數(shù)據(jù)集規(guī)模大,我們采用Local-OPT(窗口為緩存容量大小)作為本文實(shí)驗(yàn)比較目標(biāo)。

本文提出了基于查詢特性的查詢結(jié)果頁碼預(yù)測模型。在以往的研究工作中,搜索引擎查詢結(jié)果緩存系統(tǒng)通常采用 Pre-K和Pre-SDC[4]兩種預(yù)取方法。在我們的實(shí)驗(yàn)中,將其作為Baseline。

6.3 結(jié)果與分析

本文實(shí)驗(yàn)對Pre-SDC、Pre-K和提出的基于查詢特性的方法,在緩存容量5K～250K的9個(gè)容量配置下,綜合多種因素進(jìn)行實(shí)驗(yàn)。Pre-SDC的參數(shù)K在取值為1或者2處,能獲取最佳命中率(由于篇幅限制,未貼此結(jié)果)。因此,實(shí)驗(yàn)取K=0、K=1和K=2作為Pre-K和Pre-SDC的參數(shù)。

圖4 全局預(yù)測模型與緩存命中率

圖4 是全局預(yù)測模型與Pre-SDC、Pre-K、不預(yù)取、局部最佳替換策略和理論上限的對比曲線,注意,該實(shí)驗(yàn)結(jié)果默認(rèn)使用 LRU替換策略?？梢钥闯鰣D中最下面的W/o prefetching和Local-OPT曲線都是緩存沒有采取預(yù)取技術(shù)所獲得的緩存命中率,其結(jié)果均偏低,這說明搜索引擎查詢結(jié)果緩存系統(tǒng)采用預(yù)取技術(shù)對于系統(tǒng)性能提升是非常必要的。圖中最頂部的虛線為不采用預(yù)取技術(shù)的緩存命中率上界,即認(rèn)為緩存容量無限大時(shí)所獲取的命中率?？梢钥闯?在采用預(yù)取技術(shù)后,緩存容量為250K時(shí),采用預(yù)取技術(shù)的曲線已經(jīng)接近該上界。實(shí)際上,隨著緩存容量的增大(大于250K),采用預(yù)取技術(shù)的緩存命中率是會(huì)超過該理論上界的。我們提出的基于查詢特性的緩存與預(yù)取方法的緩存命中率均好于未采用預(yù)取技術(shù)的緩存命中率。由此可見,在緩存預(yù)取技術(shù)中,考慮查詢主題特性可以提高系統(tǒng)性能。

圖5 部分預(yù)測模型占總查詢百分比與緩存命中率關(guān)系

圖6 部分預(yù)測模型與緩存命中率

全局預(yù)測模型需要存儲(chǔ)全部查詢主題統(tǒng)計(jì)信息,然而,用戶瀏覽查詢結(jié)果的頁數(shù)分布具有顯著非均衡性。部分預(yù)測模型就是利用這一特性來降低信息存儲(chǔ)開銷,采用區(qū)分服務(wù)的思想來提高緩存命中率。圖5是部分預(yù)測模型的Tspec占總查詢百分比的命中率曲線。當(dāng) Tspec所占比例為0%時(shí),該方法等同于Pre-SDC方法,當(dāng)所占比例為100%時(shí),即為基于全局預(yù)測模型的緩存與預(yù)取方法。可以看出,緩存系統(tǒng)最優(yōu)命中率在 Ts pec占總查詢百分比為40%～80%之間,即基于局部預(yù)測模型可以獲得比基于全局預(yù)測模型好的緩存命中率。從圖6可以看出,與Pre-SDC、Pre-K預(yù)取策略相比,基于部分預(yù)測模型的緩存與預(yù)取方法可以獲得3.5%～8.45%的命中率提升,其效果也超過了基于全局預(yù)測模型的緩存與預(yù)取方法的命中率。同時(shí),可以注意到,緩存容量達(dá)到150K時(shí),其命中率超過了不采用預(yù)取技術(shù)的緩存命中率上界。由此可見,基于局部預(yù)測模型的緩存與預(yù)取方法,一方面,可以提高緩存系統(tǒng)命中率;另一方面,可以降低預(yù)測模型存儲(chǔ)查詢主題統(tǒng)計(jì)信息的開銷。

接下來,我們分析模型閥值選取方法對預(yù)取策略的影響。實(shí)驗(yàn)在緩存容量為50K和200K的情況下,對基于查詢特性的預(yù)測模型,測試固定閥值(以0.1遞增,從0到1變化 φ值)和動(dòng)態(tài)調(diào)整閥值方法。結(jié)果如圖7所示,基于查詢特性的預(yù)測模型在閾值采用動(dòng)態(tài)調(diào)整方法時(shí)獲得最佳緩存命中率,即圖中A、B區(qū)域顯示該結(jié)論。

圖7 基于查詢特性模型閥值對緩存命中率的影響

7 結(jié)論和進(jìn)一步研究

查詢結(jié)果緩存與預(yù)取是有效提升搜索引擎系統(tǒng)性能的關(guān)鍵技術(shù)。本文面向搜索引擎查詢結(jié)果緩存與預(yù)取問題,分析國內(nèi)某著名中文商業(yè)搜索引擎的用戶查詢?nèi)罩镜慕Y(jié)果顯示,用戶對不同查詢主題返回的查詢結(jié)果所瀏覽的頁數(shù)具有顯著的非均衡性。根據(jù)該特性,提出一種基于查詢特性的緩存與預(yù)取的方法。在該搜索引擎大規(guī)模用戶查詢?nèi)罩旧?驗(yàn)證了我們提出的方法能有效提升搜索引擎緩存系統(tǒng)命中率。

未來的工作主要集中在除了根據(jù)查詢主題頻率屬性選擇部分查詢主題集合Tspec方法外,探尋更多的選擇方法融入到本文提出的基于查詢特性的緩存與預(yù)取算法框架之中。

[1]CNNIC(China Internet Network Information Center).The 27st Report in Development of Internet in China[R].http：//research.cnnic.cn/img/h000/h12/attach201102211453210.pdf

[2]E.P.Markatos.On caching Search Engine Results[J].Computer Communications.Elsevier Science B.V..2001,24(2)：137-143.

[3]Y.Xie,D.R.O'Hallaron.Locality in Search Engine Queries and Its Implications for Caching[C]//INFOCOM'02,2002：1238-1247.

[4]T.Fagni,R.Perego,F.Sivestri,et al.Boosting the Performance of Web Search Engines：Caching and Prefetching Query Results by Exploiting Historical Usage Data[J].ACM Trans.Information Systems,2006,24(1)：51-78.

[5]Q.Gan,T.Suel.Improved Techniques for Result Caching in Web Search Engines[C]//WWW'09,ACM,2009：431-440.

[6]R.Baeze-Yates,F.Junqueira,V.Plachouras,et al.Admission Policies for Caches of Search Engine Results[C]//SPIRE'07,2007：74-85.

[7]R.Ozcan,I.S.Altingovde,et al.Static Query Result CachingRevisited[C]//WWW'08,ACM,2008：1169-1170.

[8]G.Skobeltsyn,F.Junqueira,et al.ResIn：A Combination of Results Caching and Index Pruning for High Performance Web Search Engines[C]//SIGIR'08,ACM,2008：131-138.

[9]R.Lempel,S.Moran.Predictive Caching and Prefetching of Query Results in Search Engines[C]//WWW'03,ACM,2003：19-28.

[10]班志杰,古志民,金瑜.Web預(yù)取技術(shù)綜述[J].計(jì)算機(jī)研究與發(fā)展,2009,46(2)：202-210.

[11]Y.Li,S.Zhang,B.Wang,et al.Characteristics of Chinese Web Searching：A Large-Scale Analysis of Chinese Query Logs[J].Journal of Computational Information Systems.Bethel：Binary Information Press,2008,4(3)：1127-1136.

[12]岑榮偉,劉奕群,張敏,等.基于日志挖掘的搜索引擎用戶行文分析[J].中文信息學(xué)報(bào),2010,24(3)：49-54.

[13]余慧佳,劉奕群,張敏,等.基于大規(guī)模日志分析的網(wǎng)絡(luò)搜索引擎用戶行為研究[J].中文信息學(xué)報(bào),2007,21(1)：109-114.

[14]Daniel E.Rose,Danny Levinson.Understanding User Goals in Web Search[C]//WWW'04：Proceedings of the 13th International Conference on World Wide Web.New York,NY,USA：ACM Press,2004：13-19.

[15]D.R.Slutz,I.L.Tratger.A Note on the Calculation of Average Working Set Size[J].ACM Commun.,1974,17(10)：563-565.

[16]R.L.Mattson,J.Gecsie,et al.Evaluation Techniques for Storage Hierarchies[J].IBM Systems Journal,1970,9(2)：78-117.

[17]B.G.Prieve,R.S.Fabry.VMIN-An Optimal Variable Space Page Replacement Algorithm[J].ACM Comm,1976,19(5)：295-297.