<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    posts - 9, comments - 4, trackbacks - 0, articles - 21
    搜索引擎CACHE策略研究
    一.關(guān)于搜索引擎用戶查詢得出的結(jié)論:
    (1)      用戶查詢有很大比例的重復(fù)性。有30%到40%的用戶查詢是重復(fù)查詢。
    (2)       大多數(shù)重復(fù)的用戶查詢會在較短的間隔時間被再次重復(fù)訪問。
    (3)       大多數(shù)用戶的查詢是短查詢,大約包含2-5個單詞。
    (4)       用戶一般只查看返回結(jié)果的前三個頁面(前30個返回結(jié)果)。58%用戶只查看第一個頁面(TOP 10),15%用戶查看第二個頁面,不超過12%的用戶會查看第三個頁面以后的檢索結(jié)果。
    (5)       關(guān)于用戶查詢差異程度。有比較大的查詢程度,一百萬個用戶查詢中大約63.7%的用戶查詢只出現(xiàn)過一次。另外一方面,集中的重復(fù)查詢也非常集中:25個高頻查詢大約占總查詢的1.23%-1.5%.

    二.CACHE的基本策略
    (1)       LRU:最近最少使用策略
    基本假設(shè):最近很少被重復(fù)訪問的緩存記錄在最近的將來也不會被訪問。這是最簡單的一種CACHE策略。將用戶查詢按照最近使用時間進行排序,淘汰策略將最老的查詢淘汰出CACHE。

    (2)       FBR:不僅考慮時間也考慮引用計數(shù)的問題。
    FBR在LRU策略的基礎(chǔ)上將CACHE分為三個不同的部分:NEW,OLD,MIDDLE
    NEW:存儲最近被訪問過的記錄;
    OLD:存儲最近最少使用的一批記錄;
    MIDDLE:存儲介于NEW和OLD之間的一批記錄;
    引用計數(shù)的時候不考慮NEW區(qū)域的記錄,只考慮OLD和MIDDLE兩個區(qū)域的記錄引用計數(shù)增加,在替換記錄的時候從OLD區(qū)域選擇引用計數(shù)最少的那個記錄進行替換。

    (3)       LRU/2:對于LRU的改進,計算第二次到最后一次被訪問總的LRU,將老的記錄淘汰。

    (4)       SLRU:
    CACHE被分為兩個部分:非保護區(qū)域和保護區(qū)域。每個區(qū)域的記錄都按照最近使用頻度由高到低排序,高端叫做MRU,低端叫做LRU。如果某個查詢沒有在CACHE找到,那么將這個查詢放入非保護區(qū)域的MRU端;如果某個查詢在CACHE命中,則把這個查詢記錄放到保護區(qū)的MRU端;如果保護區(qū)已滿,則把記錄從保護區(qū)放入非保護區(qū)的MRU,這樣保護區(qū)的記錄最少要被訪問兩次。淘汰的機制是將非保護區(qū)的LRU淘汰。

    (5)       LandLord策略
    將一個記錄增加到CACHE的時候,給予這個記錄一個值(DEADLINE),如果需要淘汰記錄的時候,選擇CACHE里面DEADLINE最小的那個淘汰,同時將CACHE里面其它所有記錄減去這個被淘汰的記錄的DEADLINE值,如果一個記錄被命中,則將這個記錄的DEADLINE放大到一定值。

    (6)       TSLRU:Topic based SLRU:與SLRU策略相同,不過不是按照查詢調(diào)整替換策略,而是按照查詢所屬主題進行調(diào)整。

    (7)       TLRU: Topic based LRU
    基本策略和LRU相同,區(qū)別在于保留查詢的主題(TOPIC)信息,對于某個查詢來說,不僅該主題的檢索結(jié)果進入CACHE,而且原先在CACHE里面的相同主題的查詢及其結(jié)果也調(diào)整時間,更新為最新進入CACHE??梢钥醋魇侵黝}LRU,而LRU是查詢LRU。

    (8)       PDC (probability driven cache):針對用戶的瀏覽行為建立概率模型,然后調(diào)整CACHE里面的記錄優(yōu)先級別,針對某個查詢,將用戶瀏覽數(shù)目比較多的文檔在CACHE里面的級別提高。

    (9)       預(yù)取策略
             所謂預(yù)取,就是系統(tǒng)預(yù)測用戶在很短時間內(nèi)的行為,然后將該行為涉及到的數(shù)據(jù)預(yù)先存儲在CACHE里面。存在不同的預(yù)取策略,比如預(yù)取策略:因為一般用戶在查看完第一頁檢索結(jié)果后會翻看第二頁結(jié)果,所以將該用戶查詢的第二頁結(jié)果首先預(yù)取到CACHE里面,這樣可以減少存取時間。

    (10)   二級CACHE
    有兩級CACHE,一級是查詢結(jié)果CACHE,保留了原始查詢以及相關(guān)文件;第二級CACHE是倒排文檔列表CACHE,也就是查詢中某個單詞在索引中的倒排列表信息,這個CACHE主要減少了磁盤I/O時間。替換策略采取LRU,結(jié)果證明該方法提高30%的性能。

    (11)   三級CACHE
    是對二級CACHE的一種改進策略,除了二級CACHE里面保留的兩個CACHE,另外增加一個CACHE,這個CACHE記錄了兩個單詞查詢的倒排文檔交集記錄,這樣一個是省去了磁盤I/O時間,另外一個減少了計算交集的操作,有效的減少了計算量。

    三.CACHE方法性能分析與比較
    (1)       LRU適合存儲比較小的記錄效果才好。
    (2)       中等大小的CACHE能夠滿足很大一部分重復(fù)用戶查詢。(大約20%的查詢能夠在中等大小CACHE找到)
    (3)       將時間因素和命中次數(shù)結(jié)合起來的緩存策略好于只考慮時間因素的策略。實驗表明FBR/LRU2/SLUR性能總是好于LRU策略。
    (4)       對于小CACHE來說,靜態(tài)CACHE策略要好于動態(tài)CACHE策略,命中率要高些。
    (5)       對于LRU來說,大CACHE的重復(fù)命中率大約占30%。
    (6)       對于大CACHE來說,TLRU略微好于LRU,但是差別不太大。對于小CACHE,結(jié)論正好相反。
    (7)       隨著CACHE逐步增大,命中率逐漸增加,對于SLRU來說,其性能跟兩個分區(qū)劃分大小無關(guān)。
    (8)       PDC的命中率高于LRU變形算法,大約有53%命中率,不過計算復(fù)雜度高。

     原文地址 http://blog.csdn.net/malefactor/archive/2007/01/12/1481364.aspx

    只有注冊用戶登錄后才能發(fā)表評論。


    網(wǎng)站導(dǎo)航:
     
    主站蜘蛛池模板: 日本三级在线观看免费| 久久九九全国免费| 一个人看的www在线免费视频| 久久这里只精品99re免费| 免费的涩涩视频在线播放| 亚洲成AV人片在线观看ww| 亚洲人成网站18禁止久久影院| 免费夜色污私人影院网站电影| 成人免费午夜无码视频| 国产L精品国产亚洲区久久| 亚洲一卡2卡3卡4卡5卡6卡 | 久久精品国产亚洲| 国产尤物在线视精品在亚洲| 久久久久久毛片免费播放| 久久精品国产亚洲5555| 亚洲精品无码mⅴ在线观看| 一级成人a免费视频| 亚洲一区二区女搞男| 国产综合激情在线亚洲第一页 | 亚洲Av综合色区无码专区桃色| 国产激情免费视频在线观看 | 亚洲成aⅴ人片在线观| 国产免费一区二区三区不卡| 夜夜亚洲天天久久| 国色精品va在线观看免费视频| 亚洲国产精品热久久| baoyu122.永久免费视频| 亚洲综合亚洲综合网成人| 久久久久免费看黄a级试看| 久久久久亚洲精品天堂| 四虎影视www四虎免费| 亚洲av永久无码嘿嘿嘿| 亚洲免费网站在线观看| 亚洲AV日韩AV天堂一区二区三区| 亚洲精品黄色视频在线观看免费资源| 国产大片91精品免费看3| 亚洲人成人伊人成综合网无码| 亚洲国产免费综合| 亚洲av永久无码精品网址| 国产精品色午夜视频免费看| 久久一区二区三区免费|