高性能檢索子系統(tǒng)

高性能檢索子系統(tǒng)主要內(nèi)容檢索系統(tǒng)基本技術(shù)倒排文件性能模型混合索引技術(shù)倒排文件緩存機制本章小結(jié)第2頁,共89頁，2024年2月25日，星期天主要內(nèi)容檢索系統(tǒng)基本技術(shù)倒排文件性能模型混合索引技術(shù)倒排文件緩存機制本章小結(jié)第3頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)系統(tǒng)設(shè)計與結(jié)構(gòu)索引創(chuàng)建檢索過程第4頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)系統(tǒng)設(shè)計與結(jié)構(gòu)索引創(chuàng)建檢索過程第5頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)

-系統(tǒng)設(shè)計與結(jié)構(gòu)搜索引擎檢索系統(tǒng)設(shè)計遵循的指標(biāo)檢索效率—用戶查詢的響應(yīng)時間用戶的需求是“隨心所欲的”響應(yīng)遲緩的系統(tǒng)只能意味著較少的用戶檢索效果—用戶的滿意度搜索引擎的檢索技術(shù)相對于最新的信息檢索研究成果是落后的提高檢索效果面臨的問題用戶普遍使用短查詢、不作優(yōu)化相關(guān)度計算第6頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)

-系統(tǒng)設(shè)計與結(jié)構(gòu)用戶查詢請求檢索代理布爾查詢元數(shù)據(jù)全局屬性語義約束SEServicePointIndexingServicePoint天網(wǎng)檢索系統(tǒng)集成框架結(jié)構(gòu)第7頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)

-系統(tǒng)設(shè)計與結(jié)構(gòu)天網(wǎng)檢索系統(tǒng)的設(shè)計原則系統(tǒng)效率和可擴展性通過集成的框架結(jié)構(gòu)，能夠有效地把各種有利于改善檢索效果的技術(shù)集成起來天網(wǎng)系統(tǒng)框架文檔表示用戶信息需求的類型識別不同檢索排序方式得到的結(jié)果的融合第8頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)

-系統(tǒng)設(shè)計與結(jié)構(gòu)天網(wǎng)系統(tǒng)的實現(xiàn)基于信息檢索技術(shù)排序算法和模型的選擇模型布爾模型向量空間模型檢索系統(tǒng)的相關(guān)性排序由多種因素綜合決定查詢詞的鄰接關(guān)系運算結(jié)果查詢詞出現(xiàn)的位置，包括Title、AnchorText相似度權(quán)值與其他的權(quán)值，如全局屬性的PageRank值第9頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)

-系統(tǒng)設(shè)計與結(jié)構(gòu)索引的實現(xiàn)技術(shù)采用倒排文件索引索引文件的組織結(jié)構(gòu)鏈表有利于提高更新效率，但會降低檢索效率索引項數(shù)據(jù)連續(xù)存放有利于提高檢索效率，但不利于更新索引文件的壓縮第10頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)

-系統(tǒng)設(shè)計與結(jié)構(gòu)檢索系統(tǒng)采用分布式系統(tǒng)結(jié)構(gòu)WWW1WWWnindex1index2indexNdoc1doc2docMWeb查詢服務(wù)節(jié)點索引服務(wù)節(jié)點文檔服務(wù)節(jié)點Internet檢索服務(wù)系統(tǒng)共使用20臺PC（PIII733/1GB）一臺為WWW查詢服務(wù)器，其余19臺為索引服務(wù)器，文檔服務(wù)節(jié)點和WWW查詢服務(wù)器使用同一機器第11頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)系統(tǒng)設(shè)計與結(jié)構(gòu)索引創(chuàng)建檢索過程第12頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-索引創(chuàng)建索引詞選擇索引詞的選擇是檢索系統(tǒng)實現(xiàn)的一個重要環(huán)節(jié)中文文本必須通過自動分詞程序的處理基于詞典的分詞方法基于統(tǒng)計語言模型的分詞方法英文文本統(tǒng)一轉(zhuǎn)換為小寫，但不作詞根詞形變換第13頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-索引創(chuàng)建網(wǎng)頁預(yù)處理編碼轉(zhuǎn)換GBK、GB2312、GB18030……簡繁轉(zhuǎn)換簡繁并不是一一對應(yīng)的發(fā)（發(fā)、髮），臺（臺、檯、颱）大量網(wǎng)頁不符合HTML規(guī)范、網(wǎng)頁中存在大量無用的信息（廣告、導(dǎo)航條）第14頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-索引創(chuàng)建索引創(chuàng)建算法頁面分析按HTML語法規(guī)則分析網(wǎng)頁標(biāo)簽結(jié)構(gòu)提取索引詞記錄每個索引詞的TF（詞頻）DF（文檔頻率）值通過散列表轉(zhuǎn)換為索引詞編碼，保存得到的詞典文件保存頁面分析的結(jié)果到臨時文件第15頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-索引創(chuàng)建生成臨時倒排文件根據(jù)計算的TF和DF值，可以估算出倒排文件中相應(yīng)數(shù)據(jù)項的長度，預(yù)申請整個文檔集合倒排所需要的內(nèi)存空間重新讀取頁面分析保存結(jié)果的臨時文件，在內(nèi)存中執(zhí)行倒排，把結(jié)果保存到臨時倒排文件中對生成的多個臨時倒排文件，執(zhí)行多路歸并、壓縮編碼，輸出得到最終的倒排文件第16頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)系統(tǒng)設(shè)計與結(jié)構(gòu)索引創(chuàng)建檢索過程第17頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-檢索過程索引壓縮優(yōu)點減小倒排項數(shù)據(jù)長度減少內(nèi)存和I/O帶寬的使用缺點對壓縮數(shù)據(jù)解碼，增加了CPU時間消耗方法字節(jié)對齊索引壓縮變長索引壓縮第18頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-檢索過程字節(jié)對齊索引壓縮用少量最左邊的比特位（bit）表示整數(shù)實際占用的字節(jié)數(shù)優(yōu)點容易編碼和解碼位操作少，占用CPU時間少缺點壓縮效率低每個整數(shù)至少占用一個字節(jié)的空間第19頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-檢索過程整數(shù)大小需要字節(jié)0=<x<64164=<x<16,384216,384=<x<4,194,30434,194,304=<x<1,073,741,8244可變長字節(jié)表示的整數(shù)第20頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-檢索過程變長索引壓縮一元編碼整數(shù)x編碼成x-1個比特位，后跟一個0表示結(jié)束104111071111110210511110811111110311061111109111111110第21頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-檢索過程γ編碼將整數(shù)x分成兩個部分1+[logx]和x-2[logx]1+[logx]用一元編碼實現(xiàn)x-2[logx]用[logx]比特位的二進(jìn)制編碼表示整數(shù)一元編碼γ編碼10021010031101014111011000511110110016111110110107111111011011811111110111000091111111101110001第22頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-檢索過程δ編碼將整數(shù)x分成兩個部分1+[logx]和x-2[logx]1+[logx]用γ編碼實現(xiàn)x-2[logx]用[logx]比特位的二進(jìn)制編碼表示當(dāng)整數(shù)小于15時，δ編碼比γ編碼編碼長，大于15時，δ編碼優(yōu)于γ編碼整數(shù)一元編碼γ編碼δ編碼10002101001000311010110014111011000101005111101100110101611111011010101107111111011011101118111111101110000110000009111111110111000111000001第23頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-檢索過程隨機訪問的索引組織對索引項建立二級索引，使得可以隨機訪問倒排項數(shù)據(jù)塊數(shù)據(jù)塊的大小小數(shù)據(jù)塊訪問頻繁系統(tǒng)調(diào)用尋道時間消耗較大大數(shù)據(jù)塊訪問讀入冗余數(shù)據(jù)數(shù)據(jù)傳輸時間消耗較大天網(wǎng)使用32K為最小塊單位第24頁,共89頁，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-檢索過程重要索引詞單獨索引可以產(chǎn)生小的倒排索引文件，保存在內(nèi)存中查詢在小索引文件中獲得足夠的返回結(jié)果，則查詢結(jié)束當(dāng)查詢得到的結(jié)果不足時，去訪問磁盤上的整個倒排文件重要索引詞包括AnchorText、Title，文摘中的詞第25頁,共89頁，2024年2月25日，星期天主要內(nèi)容檢索系統(tǒng)基本技術(shù)倒排文件性能模型混合索引技術(shù)倒排文件緩存機制本章小結(jié)第26頁,共89頁，2024年2月25日，星期天倒排文件性能模型大規(guī)模信息檢索系統(tǒng)的主要指標(biāo)效果：即質(zhì)量，指檢索返回結(jié)果集合的準(zhǔn)確性和完整性（準(zhǔn)確率、召回率，第十章中介紹）效率：即性能查詢響應(yīng)時間（responsetime）從用戶想系統(tǒng)提交查詢到他開始看到結(jié)果的時間間隔查詢吞吐率（throughput）系統(tǒng)在單位時間（秒）里可以服務(wù)的最大用戶查詢數(shù)量第27頁,共89頁，2024年2月25日，星期天倒排文件性能模型倒排文件的概念倒排文件的一種性能模型結(jié)合計算機性能指標(biāo)的考慮第28頁,共89頁，2024年2月25日，星期天倒排文件性能模型倒排文件的概念倒排文件的一種性能模型結(jié)合計算機性能指標(biāo)的考慮第29頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-倒排文件的概念倒排文件（InvertedFile）是描述一個詞項集合（terms）元素和一個文檔集合（docs）元素對應(yīng)關(guān)系的數(shù)據(jù)結(jié)構(gòu)詞項：可以是英文的單詞，也可以是中文的字或者詞terms={t1,t2,t3,……tM}docs={d1,d2,d3,……dN}M：詞項集合的大小N：文檔集合的大小第30頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-倒排文件的概念M詞項總數(shù)記錄表（PostingLists）不同詞項組成的索引Vocbulary每個詞項出現(xiàn)過的文檔集合第31頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-倒排文件的概念幾個相關(guān)的變量sj=|PL(tj)|詞項tj

所涉及的文檔的個數(shù)DF(tj)=sj/N詞項tj

的文檔頻率IDF(tj)=-lgDF(tj)?倒置文檔頻率，值越小表示出現(xiàn)頻率越高第32頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-倒排文件的概念fi,j第j個詞項tj

在第i個文檔di

中出現(xiàn)的次數(shù)

系統(tǒng)所有文檔包含詞項的總量（包括重復(fù)）

詞項tj

在所有文檔中出現(xiàn)的頻度ITF(tj)=-lgTF(tj)?倒置詞頻，越小表示出現(xiàn)頻率越高第33頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-倒排文件的概念M詞項總數(shù)N文檔總數(shù)sjp(i)：倒排表長度分布q1q2……qk同時到達(dá)的查詢r：響應(yīng)時間B系統(tǒng)最大輸出帶寬S：實現(xiàn)吞吐率第34頁,共89頁，2024年2月25日，星期天倒排文件性能模型倒排文件的概念倒排文件的一種性能模型結(jié)合計算機性能指標(biāo)的考慮第35頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型性能模型就是要給出N、M、p(i)、d、B、r和k的一種關(guān)系N：文檔總數(shù)M：詞項集合的大小p(i)：倒排表長度分布d：文檔平均數(shù)據(jù)量B：系統(tǒng)最大輸出帶寬r：響應(yīng)時間K：同時到達(dá)的查詢的數(shù)量第36頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型對p(i)和B的說明p(i)是倒排表長度的統(tǒng)計分布函數(shù)M*p(i)的長度表示i的記錄表的個數(shù)，i∈[0,N]倒排表的平均長度為第37頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型B是系統(tǒng)最大輸出帶寬，是支持倒排文件運行的下層系統(tǒng)的瓶頸帶寬磁盤的I/O帶寬網(wǎng)絡(luò)帶寬根據(jù)同時到達(dá)的查詢量k，得到一個數(shù)據(jù)量D，看能否有：針對查詢q1,q2,q3,……qk的假設(shè)它們都屬于集合terms它們在terms上隨機、獨立分布對于磁盤I/O帶寬和網(wǎng)絡(luò)帶寬不作區(qū)別第38頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型倒排文件性能的基本模型考察k個查詢導(dǎo)致的輸出數(shù)據(jù)量D每個查詢可能落到M個詞項中的任何一個k個查詢可能涉及M的任何1,2,……k項，對應(yīng)不同的數(shù)據(jù)量計算涉及i項的概率fm,k(i)，i=1,2,3,……k第39頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型D=一個倒排表的平均數(shù)據(jù)量*k個并發(fā)查詢平均涉及的倒排表個數(shù)第40頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型考慮全文索引與非全文索引非全文索引：只考慮哪些文檔含有特定的詞項全文索引：還要考慮該詞在相關(guān)文檔中出現(xiàn)的位置信息全文索引的情況下，每個倒排表的數(shù)據(jù)量正比于文檔號和頻率位置信息占用的長度第41頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型TN（所有文檔中詞的集合）遠(yuǎn)遠(yuǎn)大于N系統(tǒng)中每個詞項倒排表的長度主要由詞頻率TF和數(shù)據(jù)規(guī)模TN決定的平均情況下非全文索引全文索引C表示了為記錄一個詞項在文檔中一次出現(xiàn)位置信息所需的數(shù)據(jù)量第42頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型倒排表的長度影響操作執(zhí)行的時間索引網(wǎng)頁量增加時，高頻詞項的倒排表將急劇膨脹，占用大量I/O帶寬、內(nèi)存空間、CPU時間，降低系統(tǒng)效率理想情況：所有詞項頻率盡可能低，而且大小相近，使得所有倒排表同步增長。詞項的頻率分布和語言相關(guān)第43頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型頻率英語單詞（E）漢語字符（H）0.1%1032520.07%1483480.05%2204750.02%6328670.01%128512150.007%178014000.005%238116090.002%547422100.001%67132676英漢詞頻統(tǒng)計排序?qū)φ盏?4頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型英語單詞和漢語字符的ITF分布第45頁,共89頁，2024年2月25日，星期天倒排文件性能模型倒排文件的概念倒排文件的一種性能模型結(jié)合計算機性能指標(biāo)的考慮第46頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-結(jié)合計算機性能指標(biāo)的考慮決定系統(tǒng)性能的關(guān)鍵I/O的性能磁盤I/O網(wǎng)絡(luò)I/ODiskModelSize(GB)?AverageaccessTime(msec)?RPMRandomIOPSInternalTransferRate(MB/s)?InterfaceIBMUltrastar36ZX365.41000011915~29Ultra160QuantumAtlasV36.76.310000107.517~29Ultra160SeagateCheetahX1518.43.915000169.538~47FC-ALSeagateCheetah7373.45.61000011626~40Ultra160第47頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-結(jié)合計算機性能指標(biāo)的考慮提高磁盤I/O性能的方法Ultra160SCSI，最高帶寬可達(dá)150MBps當(dāng)前單個磁盤的平均數(shù)據(jù)傳輸率在20~50MBps之間解決辦法RAID：冗余磁盤陣列技術(shù)第48頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-結(jié)合計算機性能指標(biāo)的考慮系統(tǒng)吞吐量與倒排表索引的數(shù)據(jù)量假設(shè)將每個倒排表讀入內(nèi)存只需一次I/O，所花費的時間為Tlatency：磁盤訪問平均延遲時間（s）IObandwith：I/O可用帶寬（Bps）TN：所有文檔包含的詞項總量TF：頻率第49頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-結(jié)合計算機性能指標(biāo)的考慮每次讀取倒排表的時間乘Lq*m不大于1秒當(dāng)I/O系統(tǒng)性能（Tlatency、IObandwith）和TF確定下來后，可以看到TN和m之間成反比關(guān)系假設(shè)IOPS=100，Lq=5，則系統(tǒng)平均每秒處理查詢的上限是m=IOPS/Lq=20如果磁盤的可用帶寬為20MBps，則每個查詢的I/O小于1MB第50頁,共89頁，2024年2月25日，星期天倒排文件性能模型

-結(jié)合計算機性能指標(biāo)的考慮根據(jù)上式，可得出如下結(jié)論對漢字字符：TN=<400MB（TF=0.05%，Lq=5）對英文字符：TN=<4GB（TF=0.005%，Lq=5）第51頁,共89頁，2024年2月25日，星期天主要內(nèi)容檢索系統(tǒng)基本技術(shù)倒排文件性能模型混合索引技術(shù)倒排文件緩存機制本章小結(jié)第52頁,共89頁，2024年2月25日，星期天混合索引技術(shù)混合索引原理混合索引實現(xiàn)第53頁,共89頁，2024年2月25日，星期天混合索引技術(shù)混合索引原理混合索引實現(xiàn)第54頁,共89頁，2024年2月25日，星期天混合索引技術(shù)-混合索引原理索引技術(shù)面臨的問題通過自動分詞來選擇索引詞分詞單位是指具有確定語義或語法功能的基本單位目前，中文自動分詞的成熟技術(shù)都是基于分詞詞典的機械型分詞方法網(wǎng)上大量的常用詞、新出現(xiàn)詞、專業(yè)詞匯，詞典中沒有收錄分詞詞典的分詞單位一般很短，導(dǎo)致常用的短語也會被分詞程序且分開第55頁,共89頁，2024年2月25日，星期天混合索引技術(shù)-混合索引原理混合索引技術(shù)用統(tǒng)計的方法對索引文檔中的未登錄詞進(jìn)行識別，把識別出的新詞（詞典中未收錄的字串）放入一個擴展詞典有效擴大詞典的規(guī)模統(tǒng)計的方法存在相當(dāng)?shù)腻e誤率天網(wǎng)中，擴展詞典的規(guī)?？刂圃?0萬詞左右第56頁,共89頁，2024年2月25日，星期天混合索引技術(shù)-混合索引原理索引創(chuàng)建過程中首先是基于基本分詞詞典的常規(guī)分詞對基本分詞結(jié)果使用基于擴展詞典的分詞兩次的分詞結(jié)果都被選擇作為索引詞例如：基本詞典中有“國家”、“圖書館”兩個基本詞條，無“國家圖書館”系統(tǒng)通過未登錄詞識別，把“國家圖書館”加入擴展詞典文檔中出現(xiàn)“……國家圖書館……”字串，第一遍分詞得到“國家”、“圖書館”兩個基本詞條，第二遍得到“國家圖書館”最終索引詞包括“國家”、“圖書館”、“/2國家圖書館”三個單位。“/”表示轉(zhuǎn)義符，后面數(shù)字表示擴展詞包含的基本分詞詞條個數(shù)第57頁,共89頁，2024年2月25日，星期天混合索引技術(shù)-混合索引原理對用戶輸入的查詢串的處理首先是基于基本分詞詞典的常規(guī)分詞對基本分詞結(jié)果使用基于擴展詞典的分詞例如用戶輸入查詢“國家圖書館”經(jīng)過兩遍分詞，得到“國家”、“圖書館”、“/2國家圖書館”三個單位前兩個基本詞條被第三個擴展詞條覆蓋，查詢執(zhí)行時只需直接讀取索引詞“/2國家圖書館”對應(yīng)的倒排項數(shù)據(jù)，即可完成查詢第58頁,共89頁，2024年2月25日，星期天混合索引技術(shù)-混合索引原理混合索引vs.短語索引混合索引使用統(tǒng)一的倒排索引詞典，沒有額外的二級索引詞典訪問開銷混合索引不限制擴展詞條為兩個基本詞條長，可以索引更長的短語，更加靈活混合索引vs.詞索引+Bi-gram混合索引使用了未登錄詞識別技術(shù)，可以有效控制倒排索引詞典規(guī)模，避免了Bi-gram詞典膨脹的問題第59頁,共89頁，2024年2月25日，星期天混合索引技術(shù)混合索引原理混合索引實現(xiàn)第60頁,共89頁，2024年2月25日，星期天混合索引技術(shù)-混合索引實現(xiàn)未登錄詞的識別提取n元組使用基本詞典，將文本進(jìn)行部分分詞，從部分分詞結(jié)果中提取n元組單字，只有連續(xù)出現(xiàn)的單字才能生成n元組形成新詞的n元組必須包含一個單字噪聲剔除刪除那些包含低構(gòu)詞能力字的n元組第61頁,共89頁，2024年2月25日，星期天混合索引技術(shù)-混合索引實現(xiàn)剔除n元重疊把那些在n取不同值情況下重復(fù)被提取的n元組剔除最后剩下的n元組按出現(xiàn)頻次降序排列，為識別結(jié)果第62頁,共89頁，2024年2月25日，星期天混合索引技術(shù)-混合索引實現(xiàn)擴展詞典組織與分詞輸入基本分次結(jié)果序列，找到序列中在擴展詞典里的所有最長匹配詞條基本詞典和擴展詞典中的詞典均按照整數(shù)編碼進(jìn)行存放市……大學(xué)……NULL生NULL北京NULL第63頁,共89頁，2024年2月25日，星期天混合索引技術(shù)-混合索引實現(xiàn)擴展詞典匹配查找算法輸入：基本分次結(jié)果詞條序列（t1,t2,……ti）輸出：最長匹配擴展詞條init_scoreboard();初始化匹配任務(wù)表while（ti!=EOF）{code=get_code(ti);從編碼三列表中取得ti的編碼foreachtaskinscoreboard{ret=search_token(code);測匹配任務(wù)追加一個詞，是否結(jié)束？if(ret==NULL){clear_taskadd_hit;得到一個匹配}elseupdate_task;根據(jù)檢測結(jié)果更新匹配任務(wù)狀態(tài)}check_hit；檢測匹配結(jié)果，輸出}第64頁,共89頁，2024年2月25日，星期天主要內(nèi)容檢索系統(tǒng)基本技術(shù)倒排文件性能模型混合索引技術(shù)倒排文件緩存機制本章小結(jié)第65頁,共89頁，2024年2月25日，星期天倒排文件緩存機制搜索引擎檢索系統(tǒng)中通常被研究的緩存對象查詢結(jié)果用戶查詢具有很強的局部性，因此對查詢結(jié)果進(jìn)行緩存是可行的布爾操作的中間結(jié)果把布爾查詢的中間結(jié)果作為緩存對象，并利用查詢結(jié)果間的語義關(guān)系加速后續(xù)查詢的執(zhí)行倒排文件用戶查詢經(jīng)過查詢器執(zhí)行，轉(zhuǎn)換為對倒排文件數(shù)據(jù)的訪問序列，這些數(shù)據(jù)也可以作為緩存的對象第66頁,共89頁，2024年2月25日，星期天倒排文件緩存機制倒排文件緩存負(fù)載特性緩存策略的選擇第67頁,共89頁，2024年2月25日，星期天倒排文件緩存機制倒排文件緩存負(fù)載特性緩存策略的選擇第68頁,共89頁，2024年2月25日，星期天倒排文件緩存機制

-倒排文件緩存體系結(jié)構(gòu)倒排文件倒排文件緩存查詢執(zhí)行器查詢結(jié)果緩存用戶查詢結(jié)果查詢服務(wù)器索引服務(wù)節(jié)點第69頁,共89頁，2024年2月25日，星期天倒排文件緩存機制

-倒排文件緩存用戶提交的查詢中包含查詢詞的個數(shù)通常很少，詞間的位置臨近關(guān)系對結(jié)果排序十分重要天網(wǎng)使用帶位置數(shù)據(jù)的全文倒排索引，對多個詞的用戶查詢計算臨近權(quán)值查詢執(zhí)行器訪問倒排文件的數(shù)據(jù)分為兩類查詢詞對應(yīng)的倒排表中的文檔編號和文檔內(nèi)權(quán)值數(shù)據(jù)文檔數(shù)據(jù)查詢詞對應(yīng)的出現(xiàn)在每篇文檔中的位置數(shù)據(jù)位置數(shù)據(jù)第70頁,共89頁，2024年2月25日，星期天倒排文件緩存機制

-倒排文件緩存執(zhí)行過程各個查詢詞按倒置文檔頻率降序處理讀取文檔數(shù)據(jù)，執(zhí)行文檔集合的布爾運算，得到一個小的結(jié)果集合使用文檔內(nèi)權(quán)值數(shù)據(jù)計算每個結(jié)果文檔對查詢的相關(guān)性讀取對應(yīng)的位置數(shù)據(jù)，對結(jié)果集合進(jìn)行鄰近權(quán)值排序第71頁,共89頁，2024年2月25日，星期天倒排文件緩存機制

-倒排文件緩存名稱數(shù)值名稱數(shù)值用戶查詢總數(shù)7,341,383I/O序列長度1,887,198結(jié)果緩存未命中個數(shù)3,522,968I/O序列唯一對象數(shù)112,145文檔總數(shù)2,603,035PAGE序列長度20,808,025文檔數(shù)據(jù)原始大小30.18GBPAGE序列唯一對象數(shù)965,929倒排文件大小5.77GB數(shù)據(jù)集基本統(tǒng)計統(tǒng)計信息第72頁,共89頁，2024年2月25日，星期天倒排文件緩存機制倒排文件緩存負(fù)載特性緩存策略的選擇第73頁,共89頁，2024年2月25日，星期天倒排文件緩存機制-負(fù)載特性I/O序列對象大小位置數(shù)據(jù)訪問產(chǎn)生的部分是固定大小（32KB）文檔數(shù)據(jù)訪問產(chǎn)生的對象大小分布很不均勻有效的緩存替換算法需要考慮對象的大小大量的小數(shù)據(jù)對象優(yōu)先緩存，可以提高緩存的命中率大對象優(yōu)先緩存可以提高緩存的字節(jié)命中率第74頁,共89頁，2024年2月25日，星期天倒排文件緩存機制-負(fù)載特性文檔數(shù)據(jù)訪問對象大小分布第75頁,共89頁，2024年2月25日，星期天倒排文件緩存機制-負(fù)載特性序列中對象的頻度分布如果序列中對象訪問頻率分布不均勻緩存少數(shù)高頻對象可以提高性能不區(qū)分出大量低頻對象將降低性能對象訪問頻率和訪問的時間局部性是相關(guān)的頻率是倒排文件緩存替換算法應(yīng)該考慮的一個因素I/O序列的頻率特性比PAGE序列更有利于緩存第76頁,共89頁，2024年2月25日，星期天倒排文件緩存機制-負(fù)載特性I/O與PAGE序列序號--頻度分布第77頁,共89頁，2024年2月25日，星期天倒排文件緩存機制-負(fù)載特性序列中對象的時間間隔分布序列的時間局部性可以從序列中對同一個對象的兩次連續(xù)訪問的時間間隔分布來考察I/O序列可以預(yù)期得到比PAGE序列更高的緩存命中率較強的時間局部性有利于緩存的設(shè)計第78頁,共