国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于用戶特性的搜索引擎查詢結(jié)果緩存與預(yù)取

2012-10-15 01:51:40馬宏遠(yuǎn)
中文信息學(xué)報(bào) 2012年6期
關(guān)鍵詞:命中率搜索引擎頁碼

馬宏遠(yuǎn),王 斌

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

1 引言

據(jù)中國互聯(lián)網(wǎng)信息中心(CNNIC)研究報(bào)告顯示[1],截止到2009年12月31日,中國網(wǎng)民達(dá)到3.83億,其中搜索引擎使用率為73.3%,搜索引擎已經(jīng)是人們獲取信息的主要工具。一方面,互聯(lián)網(wǎng)網(wǎng)民增多,搜索引擎工作負(fù)載變大;另一方面,互聯(lián)網(wǎng)網(wǎng)頁也逐年增多,其規(guī)模已經(jīng)達(dá)到336億,且仍以年增長率超過100%的速度快速膨脹,搜索引擎需要盡可能多地索引這些網(wǎng)頁以提供準(zhǔn)確和豐富的查詢結(jié)果。在如此海量信息中,高效獲取所需查詢對(duì)學(xué)術(shù)界和工業(yè)界提出挑戰(zhàn)。自本世紀(jì)初以來,隨著互聯(lián)網(wǎng)步入高速發(fā)展時(shí)期,一些搜索引擎檢索系統(tǒng)性能優(yōu)化方法先后被提出,主要有并行處理(massively parallel processing)、索引壓縮(index com-pression)、索引裁剪(index prune)、倒排表跳轉(zhuǎn)(list skipping)、提早結(jié)束(early termination)等技術(shù)。除此之外,緩存技術(shù)(caching)與預(yù)取技術(shù)(prefetching)作為重要的系統(tǒng)性能優(yōu)化手段而被搜索引擎檢索系統(tǒng)廣泛采用和研究。

緩存作為有效減少響應(yīng)時(shí)間和系統(tǒng)負(fù)載的關(guān)鍵技術(shù),被廣泛應(yīng)用于系統(tǒng)性能優(yōu)化。查詢結(jié)果緩存通過緩存已被用戶檢索過的查詢結(jié)果以避免再次對(duì)該結(jié)果進(jìn)行排名計(jì)算帶來的CPU和磁盤讀開銷。Markatos[2]比較動(dòng)態(tài)LRU緩存替換策略以及LRU策略的若干變種和靜態(tài)緩存策略的命中率,得出靜態(tài)緩存策略對(duì)小容量緩存有效,隨著容量增大,有效性降低。Xie[3]討論緩存位置的影響,分別討論客戶端緩存、代理服務(wù)器緩存和搜索引擎服務(wù)器緩存技術(shù)。Fagni[4]提出靜態(tài)、動(dòng)態(tài)混合的緩存策略。Gan和Suel[5]提出基于查詢開銷的查詢結(jié)果緩存方法,考慮查詢頻率和開銷來對(duì)查詢結(jié)果給予不同權(quán)重。Ozcan[6]提出基于查詢穩(wěn)定度的查詢結(jié)果緩存方法,考慮查詢?cè)谝欢〞r(shí)期內(nèi)的穩(wěn)定程度來選擇查詢結(jié)果。Skobeltsyn[7]提出一種結(jié)合索引裁剪技術(shù)的查詢結(jié)果緩存方法。查詢結(jié)果預(yù)取是通過預(yù)測(cè)follow-up查詢[7],提前取得查詢結(jié)果。Lempel[8]根據(jù)查詢自身特性,建立follow-up查詢頁碼分布,提出了一種基于該分布的查詢結(jié)果預(yù)取方法。Fagni[4]通過分析查詢請(qǐng)求頁碼對(duì)follow-up查詢的影響,提出一種基于當(dāng)前請(qǐng)求查詢頁碼的自適應(yīng)查詢結(jié)果預(yù)取方法。對(duì)于Web緩存預(yù)?。?],主要是通過分析用戶訪問URL順序來預(yù)測(cè)訪問路徑,以預(yù)取用戶數(shù)據(jù)。

與以往研究不同,我們根據(jù)用戶特性來設(shè)計(jì)查詢結(jié)果緩存與預(yù)取方法,在國內(nèi)某著名商業(yè)搜索引擎日志上驗(yàn)證了我們提出方法的有效性。本文第2節(jié)分析搜索引擎用戶特性;第3節(jié)闡述基于用戶特性的查詢結(jié)果預(yù)測(cè)方法,給出全局和局部預(yù)測(cè)模型;第4節(jié)描述基于用戶特性的查詢與預(yù)取算法框架,給出算法時(shí)間復(fù)雜度和空間復(fù)雜度分析;第5節(jié)是實(shí)驗(yàn)結(jié)果及分析;第6節(jié)是本文結(jié)論以及未來工作。

2 搜索引擎用戶特性分析

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

搜索引擎系統(tǒng)的任務(wù)來源于數(shù)以百萬甚至千萬計(jì)的用戶,用戶根據(jù)自身的需求構(gòu)造一個(gè)查詢表達(dá)式提交給搜索引擎,往往不同的用戶具有不同的查詢?yōu)g覽習(xí)慣。2006年9~10月間,該搜索引擎的用戶總數(shù)約為580萬。本節(jié)將從用戶角度分析查詢結(jié)果頁瀏覽特性。圖1(a)是在該搜索引擎用戶查詢?nèi)罩旧?,統(tǒng)計(jì)用戶瀏覽查詢結(jié)果頁數(shù),其具有明顯的長尾分布特征,44%的用戶在此期間只出現(xiàn)1次查詢,往往這些用戶是系統(tǒng)的臨時(shí)用戶,而10%的用戶在此期間出現(xiàn)查詢的次數(shù)大于10。搜索引擎在做系統(tǒng)性能優(yōu)化時(shí),考慮小部分用戶的行為特性可能對(duì)系統(tǒng)性能有更多幫助,譬如搜索引擎的登錄用戶或者查詢頻率貢獻(xiàn)比較大的用戶。圖1(b)是在該搜索引擎用戶查詢?nèi)罩旧?,統(tǒng)計(jì)用戶瀏覽查詢結(jié)果頁碼相對(duì)分布(訪問查詢結(jié)果第一頁約占用戶總查詢請(qǐng)求的70%),可以看出頁碼范圍越靠前的訪問量遞減趨勢(shì)相比于相對(duì)靠后的頁碼范圍內(nèi)的訪問量遞減趨勢(shì)要明顯。

圖1 搜索引擎的用戶特性與查詢結(jié)果瀏覽

當(dāng)用戶從搜索引擎獲得部分查詢結(jié)果時(shí),會(huì)根據(jù)自身需求是否滿足等情況決定是否繼續(xù)瀏覽后續(xù)結(jié)果。當(dāng)用戶覺得當(dāng)前查詢結(jié)果頁中的結(jié)果并不滿意,其可能繼續(xù)訪問順序靠后的查詢結(jié)果頁,甚至跳躍多個(gè)頁前向訪問;在經(jīng)過一番比較后,用戶可能覺得以前的某個(gè)頁中的結(jié)果相對(duì)于當(dāng)前頁中的結(jié)果更好,這時(shí),用戶會(huì)回顧那些已經(jīng)訪問過的查詢頁中的結(jié)果或者跳過的頁中的結(jié)果。根據(jù)用戶的瀏覽行為,將用戶查詢請(qǐng)求瀏覽行為分為:(1)前向?yàn)g覽(Vf);(2)后向?yàn)g覽(Vb);(3)重復(fù)瀏覽(Vr)。我們將用戶查詢按照瀏覽行為分為以下5個(gè)集合:

A:只瀏覽第一頁;

B:瀏覽除第一頁外的頁,且其瀏覽過程行為集合為{Vf}

C:瀏覽除第一頁外的頁,且其瀏覽過程行為集合為{Vf,Vr}

D:瀏覽除第一頁外的頁,且其瀏覽過程行為集合為{Vf,Vb}

E:瀏覽除第一頁外的頁,且其瀏覽過程行為集合為{Vf,Vb,Vr}

我們對(duì)該搜索引擎用戶查詢?nèi)罩旧嫌脩舭l(fā)起的每個(gè)查詢進(jìn)行匯總。統(tǒng)計(jì)信息如圖2所示,約70%的用戶查詢只訪問第一頁結(jié)果;對(duì)于瀏覽除第一頁外的頁的用戶瀏覽行為分析,其中25%的用戶查詢存在前向?yàn)g覽行為,只有約4%的用戶查詢具有后向?yàn)g覽行為。

圖2 用戶瀏覽行為分布圖

3 搜索引擎用戶特性分析

3.1 相關(guān)定義

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

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

會(huì)話(session)是分析用戶查詢特征的重要因素,其劃分是信息檢索領(lǐng)域的一個(gè)主題,采用如下定義:同一用戶在一定時(shí)間內(nèi)帶著某些固定意圖而進(jìn)行的查詢搜索活動(dòng)。假設(shè)劃分后的會(huì)話總數(shù)為M,每個(gè)會(huì)話內(nèi)用戶u最先提交查詢的時(shí)刻定義為τj,那么,特定用戶u查詢?nèi)罩緞澐謺?huì)話可以表示為:

即用戶u的所有會(huì)話集合Su為:給初始時(shí)刻τj,該用戶后續(xù)查詢時(shí)刻距離初始時(shí)刻τj間隔小于時(shí)間長度V的所有查詢。給定用戶u,在一個(gè)會(huì)話中提交搜索查詢頁碼集合記作PSu[j],那么,用戶u的查詢頁碼集合表示為:

3.2 基于馬爾可夫鏈模型

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

那么,我們?cè)谀P驮O(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。

3.3 基于用戶特性的查詢結(jié)果預(yù)測(cè)模型

圖3 查詢請(qǐng)求頁碼狀態(tài)轉(zhuǎn)移圖

在2.1節(jié)中,我們定義了基于用戶信息來劃分用戶查詢?nèi)罩荆渲?,Pu集合是考慮用戶信息因素下歷史請(qǐng)求頁碼的分布,其會(huì)考慮用戶偏好。對(duì)于一個(gè)搜索引擎而言,通常用戶規(guī)模是數(shù)以百萬甚至千萬、億級(jí)別的,統(tǒng)計(jì)每個(gè)用戶的歷史請(qǐng)求頁碼分布需要很大的開銷。然而,用戶偏好的確可能給搜索引擎查詢結(jié)果緩存的預(yù)取帶來有用信息,以及針對(duì)有些搜索引擎支持個(gè)性化搜索,譬如用戶登錄搜索引擎,這些信息又是搜索引擎已經(jīng)記錄的。因此,我們對(duì)基于Pu的預(yù)測(cè)模型分為全局預(yù)測(cè)模型和部分預(yù)測(cè)模型。

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

全局預(yù)測(cè)模型考慮全部用戶信息,通過記錄用戶的瀏覽頁碼統(tǒng)計(jì)信息進(jìn)行預(yù)測(cè)。根據(jù)Pu集合的歷史信息,將用戶u對(duì)頁號(hào)為i訪問的次數(shù)記作Countu[i],那么,采用如下定義:

即考慮用戶的所有會(huì)話內(nèi)某個(gè)頁的分布。我們采用如下方法計(jì)算用戶查詢請(qǐng)求頁碼概率:

根據(jù)上面的定義,給定用戶當(dāng)前訪問頁號(hào)i,預(yù)測(cè)下一次用戶查詢頁碼集合Ωu,頁面訪問預(yù)測(cè)模型如下,其中,閾值φglobal用來調(diào)節(jié)預(yù)取效果:

全局預(yù)測(cè)模型認(rèn)為所有用戶都是平等的,每個(gè)用戶都使用該模型進(jìn)行瀏覽頁預(yù)測(cè),搜索引擎需要存儲(chǔ)所有用戶訪問信息,這對(duì)超大規(guī)模搜索引擎是個(gè)挑戰(zhàn)。

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

部分預(yù)測(cè)模型考慮部分用戶信息,通過記錄部分用戶的瀏覽頁碼統(tǒng)計(jì)信息進(jìn)行預(yù)測(cè)??梢赃x取登錄或則查詢頻率最高的一些用戶作為統(tǒng)計(jì)主體,這樣有益于提高個(gè)性化搜索性能。根據(jù)Pu集合的歷史信息,將用戶u對(duì)頁碼為i訪問的次數(shù)記作Countu[i],定義部分用戶集合為USpec,那么,采用如下定義:即只考慮部分用戶USpec的所有會(huì)話內(nèi)某個(gè)頁的分布。我們采用如下方法計(jì)算用戶查詢請(qǐng)求頁碼概率:

根據(jù)上面的定義,給定用戶當(dāng)前訪問頁號(hào)i,預(yù)測(cè)下一次用戶查詢頁號(hào)集合Ωu,頁面訪問預(yù)測(cè)模型如下,其中閾值φuser用來調(diào)節(jié)預(yù)取效果:

與全局預(yù)測(cè)模型不同的是,部分預(yù)測(cè)模型只考慮部分用戶USpec的瀏覽頁分布,搜索引擎只需要存儲(chǔ)部分用戶訪問信息,這樣可能降低搜索引擎為存儲(chǔ)這些統(tǒng)計(jì)信息所需要的開銷。

3.4 模型閾值選取方法

我們采用如下兩種方法來確定閾值:(1)設(shè)置固定閾值,采用固定值,需要預(yù)先設(shè)定,閾值與當(dāng)前瀏覽頁碼無關(guān);(2)根據(jù)總體瀏覽頁碼分布動(dòng)態(tài)調(diào)整閾值,閾值與當(dāng)前瀏覽頁碼有關(guān)。

4 算法框架

在第3節(jié),我們給出結(jié)合用戶特性的預(yù)測(cè)方法。本節(jié)將在此基礎(chǔ)上,給出結(jié)合用戶特性的緩存與預(yù)取算法框架,如算法1所示。在搜索引擎環(huán)境下,有必要對(duì)查詢結(jié)果預(yù)取做一些必要規(guī)則。

規(guī)則1:在一個(gè)會(huì)話內(nèi),搜索引擎收到用戶的一個(gè)查詢主題的首次請(qǐng)求不為第一頁時(shí),不對(duì)該用戶的查詢結(jié)果做預(yù)取。

用戶向搜索引擎發(fā)起一個(gè)查詢請(qǐng)求,通常會(huì)返回查詢結(jié)果的第一頁。然而,一些網(wǎng)絡(luò)查詢代理程序可能會(huì)首次請(qǐng)求第二頁,并不需要對(duì)這些查詢請(qǐng)求做預(yù)取優(yōu)化,原因在于,其并不是搜索引擎的真正用戶。提高網(wǎng)絡(luò)代理程序的性能是以占取搜索引擎為真正用戶服務(wù)的資源為代價(jià)。

規(guī)則2:以查詢結(jié)果頁碼的自然順序做預(yù)取。

用戶在查詢時(shí),通常按照自然順序訪問查詢結(jié)果頁,總體上,約96%的查詢請(qǐng)求訪問查詢結(jié)果頁的行為是非逆序的。該規(guī)則也是預(yù)取模型的基本假設(shè)。

規(guī)則3:只有當(dāng)瀏覽查詢結(jié)果頁碼的概率大于閾值才做預(yù)取。

搜索引擎緩存系統(tǒng)的存儲(chǔ)容量是有限的,一次錯(cuò)誤的預(yù)取行為會(huì)造成緩存存儲(chǔ)容量的浪費(fèi),即可能使有用的條目被替換出緩存。因此,并不是簡單以某一瀏覽頁碼被訪問概率大于不被訪問概率為條件,而是,使用閾值來調(diào)節(jié)預(yù)取行為。

規(guī)則4:對(duì)于部分預(yù)測(cè)模型,搜索引擎緩存系統(tǒng)首先查詢?cè)摬糠炙鶎?duì)應(yīng)的緩存,如果不命中,再去查詢其他部分緩存。

對(duì)于搜索引擎的部分預(yù)測(cè)模型,緩存系統(tǒng)根據(jù)某些屬性分為多塊緩存,如根據(jù)用戶信息分類。當(dāng)收到用戶的某一查詢主題時(shí),根據(jù)查詢結(jié)果訪問的空間局部性,即通過局部預(yù)測(cè)模型預(yù)取用戶可能訪問的查詢結(jié)果頁碼,緩存系統(tǒng)應(yīng)該首先在該用戶所對(duì)應(yīng)的查詢結(jié)果緩存中查詢,以提高緩存檢索相關(guān)條目操作的效率。

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

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

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

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

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

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

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

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

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

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

5.3 結(jié)果與分析

本文實(shí)驗(yàn)對(duì)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ù)。

圖5是全局預(yù)測(cè)模型與 Pre-SDC、Pre-K、不預(yù)取、局部最佳替換策略和理論上限的對(duì)比曲線,注意,該實(shí)驗(yàn)結(jié)果默認(rèn)使用LRU替換策略??梢钥闯鰣D中最下面的 W/o prefetching和Local-OPT曲線都是緩存沒有采取預(yù)取技術(shù)所獲得的緩存命中率,其結(jié)果均偏低,這說明搜索引擎查詢結(jié)果緩存系統(tǒng)采用預(yù)取技術(shù)對(duì)于系統(tǒng)性能提升是非常必要的。圖中最頂部的虛線為不采用預(yù)取技術(shù)的緩存命中率上界,即認(rèn)為緩存容量無限大時(shí)所獲取的命中率??梢钥闯?,在采用預(yù)取技術(shù)后,緩存容量為250K時(shí),采用預(yù)取技術(shù)的曲線已經(jīng)接近該上界。實(shí)際上,隨著緩存容量的增大(大于250K),采用預(yù)取技術(shù)的緩存命中率是會(huì)超過該理論上界?;谟脩籼匦裕≒re-GlUser+phi_0.1)(此時(shí),φ=0.1,關(guān)于φ選取方法對(duì)預(yù)測(cè)模型的影響在后面實(shí)驗(yàn)分析)預(yù)取的緩存命中率均好于未采用預(yù)取技術(shù)的緩存命中率。然而,基于全局預(yù)測(cè)模型的效果比基于Pre-SDC和Pre-K效果要差。由此可見,基于用戶特性的方法需要考慮用戶群體內(nèi)部的差異,如我們?cè)诘?節(jié)分析搜索引擎用戶特性所顯示,往往某些用戶占據(jù)了大部分查詢請(qǐng)求現(xiàn)象。

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

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

基于全局信息的預(yù)測(cè)模型需要額外信息存儲(chǔ)開銷,然而,用戶往往是不對(duì)稱的?;诓糠钟脩粜畔⒌念A(yù)測(cè)模型就是利用這一特性來降低信息存儲(chǔ)開銷,采用區(qū)分服務(wù)的思想來提高部分和整體命中率。在訓(xùn)練集中選取該搜索引擎查詢頻率最高的14 748個(gè)用戶(約占總用戶數(shù)的0.25%,總共用戶為5 809 111)作為部分用戶集合,分配10%的緩存容量給這部分用戶作為部分用戶緩存。圖6是基于部分用戶信息的預(yù)測(cè)模型與其他方法的對(duì)比。實(shí)驗(yàn)結(jié)果表明,該方法可以獲得3.03%~4.17%的命中率提升,對(duì)我們選定的用戶集合獲得20.52%~28.2%的命中率提升(如圖7(a)所示)。

圖7是采用部分信息的預(yù)測(cè)模型前后,該用戶集合緩存命中率和緩存系統(tǒng)總體命中率的對(duì)比(由于篇幅限制,只貼出Pre-SDC1比較圖,其他方法與此結(jié)論類似)。從用戶集合命中率對(duì)比圖7(a)來看,這14 748個(gè)用戶的命中率得到大幅提升。一方面,通過給予這部分用戶更多的緩存空間,使他們所需要的查詢能夠盡量緩存住;另一方面,這部分用戶相比其他用戶,對(duì)搜索引擎查詢請(qǐng)求貢獻(xiàn)更大。從總體緩存角度來看,其命中率也得到提升。由此可見,本文提出的基于部分用戶緩存與預(yù)取的方法,一方面,可以降低全局預(yù)測(cè)模型存儲(chǔ)用戶信息開銷;另一方面,通過對(duì)不同部分用戶劃分不同容量可以提高部分用戶的查詢命中率,即提高這部分用戶的查詢檢索性能,與此同時(shí),可以提高緩存總體命中率。

圖7 部分用戶集合與所有用戶集合緩存命中率

圖8 基于用戶特性模型閾值對(duì)緩存命中率的影響

接下來,我們分析模型閾值選取方法對(duì)模型的影響。實(shí)驗(yàn)在緩存容量為50K和200K的情況下,對(duì)基于用戶特性的預(yù)測(cè)模型,測(cè)試固定閾值(以0.1遞增,從0到1變化φ值)和動(dòng)態(tài)調(diào)整閾值方法,結(jié)果如圖8所示,基于用戶特性的預(yù)測(cè)模型在閾值靜態(tài)設(shè)置為0時(shí)獲得最佳緩存命中率,即圖中A、B區(qū)域。因此,當(dāng)使用基于用戶預(yù)測(cè)模型時(shí),建議采用靜態(tài)閾值方法,將其值設(shè)置為0。需要指出的是,我們?cè)谇懊娴膶?shí)驗(yàn)中,通過設(shè)置靜態(tài)閾值為0.1驗(yàn)證基于用戶特性的預(yù)測(cè)模型(含閾值)和算法框架的有效性。實(shí)際上,通過調(diào)節(jié)該靜態(tài)閾值,系統(tǒng)性能是能夠進(jìn)一步有所提升的。然而,其代價(jià)是增加搜索引擎檢索排序系統(tǒng)的負(fù)載。關(guān)于模型閾值與檢索排序系統(tǒng)負(fù)載的關(guān)系是本文需要的進(jìn)一步工作。

6 結(jié)論及未來工作

查詢結(jié)果緩存與預(yù)取是有效提升搜索引擎系統(tǒng)性能的關(guān)鍵技術(shù)。本文面向搜索引擎查詢結(jié)果緩存與預(yù)取問題,提出一種基于用戶特性的緩存與預(yù)取的方法,該方法包括用來指導(dǎo)預(yù)取的查詢結(jié)果預(yù)測(cè)模型和基于用戶特性的分區(qū)緩存。通過在國內(nèi)某著名搜索引擎大規(guī)模用戶查詢?nèi)罩旧系膶?shí)驗(yàn),討論用戶信息選取范圍(全局和局部)、閾值選取方法等問題。實(shí)驗(yàn)結(jié)果表明,該方法可以有效提升搜索引擎緩存命中率,尤其對(duì)搜索引擎系統(tǒng)查詢量的貢獻(xiàn)較大的用戶群體更為顯著。

未來的工作集中在三個(gè)方面,一是探尋更多的用戶特性融入到本文提出的基于用戶特性的緩存與預(yù)取框架之中;二是研究選定用戶集合大小與該集合分配緩存容量關(guān)系對(duì)整體緩存命中率的影響;三是討論模型閾值選取對(duì)搜索引擎檢索排序系統(tǒng)的負(fù)載影響。

除此之外,當(dāng)今的搜索引擎系統(tǒng)對(duì)實(shí)時(shí)索引更新有重要需求,由于索引更新,導(dǎo)致緩存的查詢結(jié)果陳舊。因此,如何保證緩存一致性成為一個(gè)重要挑戰(zhàn),文獻(xiàn)[16-18]已取得一定成果。在該場景下,考慮用戶特性是我們未來可能嘗試的工作。

[1]CNNIC(China Internet Network Information Center).The 25th report in development of Internet in China[DB/OL].http://www.cnnic.net.cn/uploadfiles/pdf/2010/1/15/101600.pdf.2010.

[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]//Proceedings of INFOCOM'02,2002:1238-1247.

[4]T.Fagni,R.Perego,F(xiàn).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]//Proceedings of WWW'09,ACM,2009:431-440.

[6]R.Ozcan,I.S.Altingovde,et al.Static query result caching revisited [C]//Proceedings of WWW'08,ACM,2008:1169-1170.

[7]G.Skobeltsyn,F(xiàn).Junqueira,et al.ResIn:A combination of results caching and index pruning for high performance web search engines[C]//Proceedings of SIGIR'08,ACM,2008:131-138.

[8]R.Lempel,S.Moran.Predictive caching and prefetching of query results in search engines[C]//Proceedings of WWW'03,ACM,2003:19-28.

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

[10]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.

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

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

[13]D.R.Slutz,I.L.Tratger.A note on the calculation of average working set size[J].ACM Commun.,1974,17(10):563-565.

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

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

[16]B.B.Cambazoglu,F(xiàn).P.Junqueira,V.Plachouras,et al.A refreshing perspective of search engine caching[C]//Proceedings of WWW'10,ACM,2010:181-190.

[17]R.Blanco,E.Bortnikov,F(xiàn).Junqueira,et al.Caching search engine results over incremental indices[C]//Proceedings of SIGIR'10,ACM,2010:82-89.

[18]S.Alici,I.S.Altingovde,R.Ozcan,et al.Timestamp-based Result Cache Invalidation for Web Search Engines[C]//Proceedings of SIGIR'11,ACM,2011:973-982.

猜你喜歡
命中率搜索引擎頁碼
Nonlinear Dynamic Analysis and Fatigue Study of Steep Wave Risers Under Irregular Loads
CONTENTS OF 2020
特種油氣藏(2020年6期)2020-01-05 10:24:40
夜夜“奮戰(zhàn)”會(huì)提高“命中率”嗎
2015男籃亞錦賽四強(qiáng)隊(duì)三分球進(jìn)攻特點(diǎn)的比較研究
長江叢刊(2018年31期)2018-12-05 06:34:20
投籃的力量休斯敦火箭
NBA特刊(2017年8期)2017-06-05 15:00:13
Consequences of early adverse rearing experience(EARE) on development: insights from non-human primate studies
算頁碼
網(wǎng)絡(luò)搜索引擎亟待規(guī)范
試析心理因素對(duì)投籃命中率的影響
基于Nutch的醫(yī)療搜索引擎的研究與開發(fā)
临潭县| 乐平市| 米林县| 岗巴县| 云梦县| 延吉市| 永年县| 宁南县| 印江| 新建县| 桑日县| 浪卡子县| 兰考县| 东兰县| 澄迈县| 壤塘县| 崇文区| 保定市| 吐鲁番市| 武安市| 吉木乃县| 西和县| 理塘县| 宜城市| 锦州市| 哈巴河县| 龙山县| 安平县| 江永县| 巴林左旗| 托克逊县| 随州市| 布尔津县| 龙泉市| 西林县| 竹北市| 富裕县| 津市市| 兖州市| 兰溪市| 明水县|