一種改進(jìn)的分布式搜索引擎模型

錢立兵，季振洲，吳 昊

(哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，150001哈爾濱)

大規(guī)模文檔數(shù)據(jù)使得分布式引擎的檢索和查詢都面臨性能的壓力，為了提高分布式搜索模型的性能，在索引合并和查詢算法方面，很多學(xué)者開展了研究工作.針對(duì)索引合并，Heinz等［1］討論了合并的索引構(gòu)建方法及其相對(duì)于排序方法的優(yōu)勢(shì);Büttcher等［2］研究了 Logarichmic 合并算法并驗(yàn)證該算法對(duì)于索引合并的高效性;Hao等 提出對(duì)索引壓縮和查詢預(yù)處理來優(yōu)化文檔排序.關(guān)于查詢算法，document-at-a-time(DAAT)和termat-a-time(TAAT)是兩種經(jīng)典的算法［4-5］;Turtle等［6］根據(jù)詞項(xiàng)的最大得分策略(max score)優(yōu)化了查詢過程;Strohman等［7］使用預(yù)處理剪裁前k個(gè)最好結(jié)果的得分下界改進(jìn)查詢效率.然而，這些改進(jìn)均建立在傳統(tǒng)模型基礎(chǔ)上，并沒有改變傳統(tǒng)模型自身的一些局限，如宏觀上索引文檔結(jié)構(gòu)劃分的無序性，用戶全局性查詢的盲目性以及系統(tǒng)擴(kuò)展性不強(qiáng)等.

本文優(yōu)化了傳統(tǒng)分布式搜索模型的結(jié)構(gòu)，按照文檔主題對(duì)索引文檔進(jìn)行分類，提出高效、可擴(kuò)展的并行分布式模型結(jié)構(gòu);以優(yōu)化模型為基礎(chǔ)，改進(jìn)索引倒排表結(jié)構(gòu)，并利用MaxScore策略，對(duì)堆排序進(jìn)行優(yōu)化，設(shè)計(jì)出針對(duì)索引節(jié)點(diǎn)的并行查詢算法.

1 傳統(tǒng)分布式搜索引擎

1.1 分布式搜索模型

分布式搜索引擎有沙漏模型、Map/Reduce模型、P2P網(wǎng)絡(luò)模型等，其中，沙漏模型應(yīng)用最為廣泛.圖1是經(jīng)典的沙漏模型［8］，系統(tǒng)包含前端應(yīng)用展現(xiàn)層(processing of front，PF)、結(jié)果匯聚層(merge)和獨(dú)立引擎層(search engine，SE).

圖1 分布式引擎的沙漏模型結(jié)構(gòu)

PF層主要處理不同業(yè)務(wù)需求，每一類應(yīng)用都會(huì)根據(jù)該應(yīng)用特征解析query，然后訪問merge層.merge層起到承上啟下作用，接受PF層傳遞的多個(gè)請(qǐng)求，向SE層多個(gè)獨(dú)立引擎發(fā)送;合并各個(gè)引擎請(qǐng)求結(jié)果后發(fā)送給PF層.SE層是分布式引擎系統(tǒng)中的基礎(chǔ)層，承擔(dān)海選、相關(guān)性、精選等過程，是系統(tǒng)搜索核心過程.

1.2 分布式查詢過程

PF層接收用戶請(qǐng)求(query)，經(jīng)過詞干提取、用戶行為、查詢意圖［10-11］分析得到若干個(gè)特征詞{q1，q2，…，qm}，再由 merge 層將這些特征詞轉(zhuǎn)發(fā)到SE層的各個(gè)獨(dú)立引擎.每個(gè)獨(dú)立引擎根據(jù)特征詞對(duì)其倒排表進(jìn)行海選、普通排序、精排，堆排序得到各自Top N結(jié)果.merge層根據(jù)SE層的各個(gè)獨(dú)立引擎所得到結(jié)果集，進(jìn)行除重、過濾、相關(guān)性排序得到最終Top N個(gè)結(jié)果，返回用戶.若獨(dú)立引擎數(shù)為n，特征詞數(shù)目為m，則用戶一次請(qǐng)求在merge層會(huì)產(chǎn)生獨(dú)立引擎查詢次數(shù)m*n．

這種分布式查詢過程使得整個(gè)系統(tǒng)處于繁忙狀態(tài).高并發(fā)用戶請(qǐng)求，使得merge層的請(qǐng)求任務(wù)與結(jié)果合并任務(wù)成倍增加;同時(shí)索引節(jié)點(diǎn)的增加，也會(huì)導(dǎo)致merge層增加負(fù)載任務(wù).因此，如何提高系統(tǒng)擴(kuò)展性，適應(yīng)高并發(fā)查詢是搜索引擎研究的關(guān)鍵目標(biāo)之一.

2 并行分布式搜索

2.1 并行模型提出

為了克服沙漏模型的不足，本文根據(jù)文檔主題對(duì)文檔集進(jìn)行分類，建立分類索引.文檔主題的分類方法是根據(jù)用戶的請(qǐng)求，提取用戶查詢特征詞，以特征詞代表文檔，按照二元分類方法的NN算法［12］，計(jì)算各種類別模式下特征詞的得分，與最低閥值比較，保留大于最低閥值的類別作為分類結(jié)果.特征詞的提取按照文獻(xiàn)［13］的詞項(xiàng)權(quán)重為

式中:wt，d為詞 t在文檔 d 中權(quán)重;tft，d為詞 t在文檔d中的詞頻;N為文檔總數(shù);dft為出現(xiàn)t的所有文檔數(shù)．

按照主題分類使得有些文檔可能屬于多個(gè)類別(跨類文檔)，對(duì)于這種跨類文檔，可以采用簡單的URL近似匹配，前提要對(duì)各個(gè)類別保存主體的URL前綴，具體做法是對(duì)跨類文檔的URL分別匹配所屬類別的URL集，保留URL匹配的最大文檔，確定跨類文檔最終只屬于一個(gè)類別，按照單個(gè)類別建立索引.

圖2是基于傳統(tǒng)的分布式引擎所設(shè)計(jì)的可擴(kuò)展的分布式模型.在merge層，按照文檔主題建立1～M個(gè)類別的索引集，每個(gè)merge節(jié)點(diǎn)管理一類索引節(jié)點(diǎn)，例如merge1節(jié)點(diǎn)管理索引Index(1，1)～I(xiàn)ndex(1，c1)節(jié)點(diǎn)，使得查詢請(qǐng)求所訪問的索引節(jié)點(diǎn)具有針對(duì)性.

圖2 具有分類索引結(jié)構(gòu)的分布式模型結(jié)構(gòu)

依據(jù)圖2建立的模型，分類查詢過程如下:當(dāng)應(yīng)用層得到用戶查詢請(qǐng)求query后，經(jīng)過分詞得到查詢關(guān)鍵詞Keyword，由Keyword確定待查詢的merge節(jié)點(diǎn)，被觸發(fā)的merge節(jié)點(diǎn)查詢本類索引節(jié)點(diǎn)，查找的結(jié)果返回到merge層，merge層合并本類索引節(jié)點(diǎn)的結(jié)果返回給應(yīng)用層.

該模型的查詢類別識(shí)別方法為:首先，應(yīng)用層需要保存merge層各個(gè)類別模式的特征詞和近義詞，匹配用戶查詢Keyword;然后，應(yīng)用層根據(jù)識(shí)別類別向所屬的所有類別的merge層發(fā)送請(qǐng)求，被觸發(fā)的merge節(jié)點(diǎn)再按照本節(jié)點(diǎn)的文檔類別訪問獨(dú)立引擎層的索引節(jié)點(diǎn).如圖2所示，merge層只是被動(dòng)接收應(yīng)用層發(fā)送的請(qǐng)求，識(shí)別用戶過程由應(yīng)用層負(fù)責(zé)，這樣能夠提早識(shí)別出類別，避免全局查找.

2.2 索引倒排表的改進(jìn)

上述建立的并行模型，對(duì)于倒排記錄經(jīng)常發(fā)生變化的文檔集合，需要更好的索引結(jié)構(gòu).索引合并是檢索系統(tǒng)的重要任務(wù).一種優(yōu)化歸并的方法是采用跳表(skip list)［14］策略能夠獲得很好的性能，即在構(gòu)建索引時(shí)構(gòu)建一個(gè)跳表，當(dāng)跳表指針的目標(biāo)項(xiàng)小于另一個(gè)表的當(dāng)前比較項(xiàng)時(shí)可以采用跳表指針直接跳過.如圖3所示，對(duì) t1=“Information”和t2=“Retrieval”進(jìn)行合并，假如t1的指針移到17，t2的指針移到65，較小項(xiàng)為17．此時(shí)并不需要移動(dòng)t1，而是檢查跳表指針，此時(shí)為30，仍然比65小，t1直接跳到30，即跳過了21和24．

圖3 帶有跳表指針的倒排記錄表

倒排記錄經(jīng)常發(fā)生變化的文檔，使得倒排記錄表指針頻繁發(fā)生變化，從而喪失了跳表的性能.為了解決跳表結(jié)構(gòu)的性能問題，對(duì)于較長的倒排表的詞項(xiàng)設(shè)計(jì)一個(gè)位圖(Bitmap)結(jié)構(gòu)(考慮Bitmap結(jié)構(gòu)本身的內(nèi)存開銷，較短的記錄表無須設(shè)計(jì)Bitmap).Bitmap結(jié)構(gòu)的存儲(chǔ)順序號(hào)與文檔ID對(duì)應(yīng)，若文檔存在倒排記錄表中，對(duì)應(yīng)位標(biāo)記為1，否則為0.例如:ID=1 027的文檔記錄在第1 027 bit存儲(chǔ)位，即存儲(chǔ)在Bitmap結(jié)構(gòu)的第128 B的第3位(1 027=128*8+3).

如圖 4所示，對(duì) t1=“Information”、t2=“Retrieval”和 t3=“Organization”，對(duì)較長倒排列表的詞項(xiàng)t1和t2建立Bitmap，t3鏈表長度較短無需建立Bitmap，先對(duì)t1和t2的Bitmap合并保存到中間的Bitmap merge中，再遍歷t3得到記錄表的文檔號(hào)，添加到Bitmap merge，即得到合并結(jié)果.

圖4 帶有Bitmap結(jié)構(gòu)的倒排記錄表

本文針對(duì)較長記錄表的選擇依據(jù)設(shè)計(jì)了兩種方法:1)采用固定常數(shù)γ，記錄大于γ時(shí)建立Bitmap;2)設(shè)計(jì)一個(gè)可調(diào)參數(shù)λ(0＜λ＜1)，設(shè)文檔集數(shù)目N，L(t)為詞項(xiàng)t的倒排表長度，當(dāng)L(t)＞λN時(shí)，建立Bitmap.兩種方法中γ或λ需要通過根據(jù)內(nèi)存容量情況去選擇．

對(duì)于k個(gè)長度為L的記錄表合并，普通算法采用多路合并，時(shí)間復(fù)雜度為O(L*k*lg k)．采用Bitmap策略時(shí)，滿足條件的倒排記錄表建立Bitmap的時(shí)間復(fù)雜度為O(k*t)，即k個(gè)Bitmap按位運(yùn)算時(shí)間開銷(t為兩個(gè)Bitmap合并開銷，通常為常量)，提高了查詢速度.空間上需要對(duì)每個(gè)較長記錄表設(shè)計(jì) N位的 Bitmap，即建立O(r*N/8)(r為滿足建立Bitmap條件的記錄表個(gè)數(shù)).在查詢過程中，對(duì)多個(gè)查詢?cè)~的請(qǐng)求，先對(duì)詞項(xiàng)的Bitmap合并(對(duì)于不存在Bitmap結(jié)構(gòu)的詞項(xiàng)，按照正常的遍歷方式得到文檔號(hào)信息，然后加入到Bitmap結(jié)構(gòu)中).在動(dòng)態(tài)更新文檔時(shí)，只需要添加或刪除Bitmap中對(duì)應(yīng)的文檔號(hào)位置.較少的內(nèi)存空間開銷所帶來倒排表合并的速度優(yōu)勢(shì)很重要，對(duì)較長鏈表直接進(jìn)行位圖合并，能夠較好地提高查詢速度.在實(shí)際應(yīng)用中，根據(jù)內(nèi)存開銷允許的程度去選擇γ或λ，對(duì)倒排記錄表選擇建立Bitmap結(jié)構(gòu)，能夠優(yōu)化系統(tǒng)性能.

2.3 并行查詢算法設(shè)計(jì)

針對(duì)文中設(shè)計(jì)的搜索模型，提出一種優(yōu)化的并行查詢算法.查詢算法中的評(píng)分函數(shù)是依據(jù)Robertson 等［15］使用的 Okapi BM25.

式中:N為文檔集數(shù)量;Nt為包含詞項(xiàng)t的文檔數(shù);ft，d為詞項(xiàng)t在文檔d中出現(xiàn)次數(shù);k1(默認(rèn)是1.2)用來調(diào)節(jié)TF的飽和度;b(默認(rèn)是0.75)用于歸一化文檔長度;ld為文檔d詞條數(shù);lavg為文檔集中所有文檔平均詞條數(shù)．

算法中設(shè)計(jì)3類數(shù)據(jù)結(jié)構(gòu):詞項(xiàng)(term)堆用于管理查詢?cè)~項(xiàng){t1，t2，…，tm}，追蹤每個(gè)查詞項(xiàng)項(xiàng)t的下一個(gè)文檔;Bitmapmerge結(jié)構(gòu)(位圖結(jié)構(gòu))用于存儲(chǔ)倒排表合并后文檔ID的存在狀態(tài);result堆用于維護(hù)當(dāng)前找到的Top k個(gè)搜索結(jié)果．采用線程池(thread pool)分配和管理3類數(shù)據(jù)結(jié)構(gòu)，每個(gè)線程都有獨(dú)立的3種結(jié)構(gòu)，線程初始化時(shí)構(gòu)建3類數(shù)據(jù)結(jié)構(gòu)，3種結(jié)構(gòu)都是隨著當(dāng)前用戶的查詢?cè)~項(xiàng)加入，查詢結(jié)束后清空.

如圖5所示，對(duì)于查詢?cè)~集合 queryterms={“computer”，“science”，“technical”}，啟動(dòng)線程池中的線程1，建立3個(gè)元素的term堆，分配一個(gè)Bitmap merge，同時(shí)分配含Top k的result堆(按得分建立小根堆).term堆中每個(gè)詞項(xiàng)連接的文檔按照ID排序，result堆在運(yùn)行中保存當(dāng)前最好的k個(gè)文檔，根節(jié)點(diǎn)是當(dāng)前第k個(gè)最好的文檔，當(dāng)找到一個(gè)新文檔比根節(jié)點(diǎn)分?jǐn)?shù)高時(shí)，利用新文檔替換根節(jié)點(diǎn)，進(jìn)而調(diào)整堆結(jié)構(gòu).

圖5 線程池結(jié)構(gòu)與并行查詢方法示例

根據(jù)turtle和flood的maxscore策略優(yōu)化查詢過程，式(2)中 TF得分貢獻(xiàn)不超過 k1+1=2.2(k1取默認(rèn)值1.2)，即詞項(xiàng)總得分不超過2.2lg(N/Nt)．改進(jìn)的查詢算法采用了此種技術(shù)優(yōu)化查詢過程．

在支撐多核的硬件平臺(tái)下，設(shè)計(jì)thread pool結(jié)構(gòu)管理并行執(zhí)行的線程.倒排記錄表作為所有查詢線程的公共訪問資源，查找過程不會(huì)改變公共資源，因此對(duì)倒排列表的訪問本身存在高度并發(fā)訪問優(yōu)點(diǎn).由于線程本身開啟和切換存在開銷，盡可能使分配的線程任務(wù)飽滿，而不是分配過多的任務(wù)量輕的線程.

對(duì)于搜索引擎業(yè)務(wù)，設(shè)請(qǐng)求任務(wù)并發(fā)數(shù)為n/s，線程最大處理任務(wù)數(shù)為Cmax，為了避免過多的輕量線程開銷，要求每個(gè)線程至少處理任務(wù)數(shù)為Cmin，線程池最多數(shù)目為p(由硬件限制，一般為核數(shù)2倍最優(yōu))，實(shí)際開啟線程數(shù)Pnum．當(dāng)n≤Cmin*p時(shí)，Pnum=n/Cmin，即開啟n/Cmin個(gè)線程;當(dāng)Cmin*p＜n≤Cmax*p時(shí)，開啟的線程數(shù)Pnum=2*p/(Cmin+Cmax);當(dāng)n＞Cmax*p時(shí)，線程處于超負(fù)載情況，充分利用硬件資源，開啟Pnum=p個(gè)線程．通過實(shí)驗(yàn)測(cè)得Cmin=2，Cmax=6，即任務(wù)數(shù)小于2時(shí)，屬于輕量線程;任務(wù)數(shù)大于6時(shí)，屬于超負(fù)荷線程．

圖6 對(duì)堆排序裁剪的一種多線程并行查詢算法

通過上述計(jì)算得到開啟線程數(shù)Pnum，得到如圖6所示的MMSH算法，每次處理n個(gè)請(qǐng)求queryList［1…n］:每個(gè)線程平均處理任務(wù)數(shù)n/Pnum．每個(gè)線程調(diào)用改進(jìn)的堆排序裁減MSH(max score heap)算法處理請(qǐng)求任務(wù)，如圖7所示.

圖7 MSH算法

MMSH算法的核心處理是MSH算法，如圖7所示，通過對(duì)堆排序的剪裁，在保證結(jié)果一致性情況下，優(yōu)化了查詢性能.MSH算法能夠保證算法的結(jié)果與堆排結(jié)果一樣，但速度要快很多，這是因?yàn)橐坏┌l(fā)現(xiàn)某個(gè)文檔不可能為前k個(gè)結(jié)果，立即被忽略.

3 實(shí)驗(yàn)與討論

硬件資源:IBMX360f服務(wù)器，16核處理器、16 G內(nèi)存;通過商業(yè)引擎Ha3+hadoop技術(shù)，分別構(gòu)建如圖1的分布式引擎的沙漏模型(Search1)和如圖2改進(jìn)的分布式引擎(Search2)架構(gòu).通過比較改進(jìn)模型和傳統(tǒng)模型的查詢算法效率和系統(tǒng)吞吐量，說明設(shè)計(jì)的有效性.

1)實(shí)驗(yàn)環(huán)境搭建.為了實(shí)驗(yàn)條件的一致性，兩種結(jié)構(gòu)均使用8個(gè)節(jié)點(diǎn)服務(wù)器.Search1和Search2都使用4個(gè)索引節(jié)點(diǎn)，2個(gè)merge節(jié)點(diǎn)，2個(gè)PF節(jié)點(diǎn).

2)實(shí)驗(yàn)數(shù)據(jù).借助于商業(yè)引擎的Hadoop集群抓取得到50 G文檔數(shù)據(jù);查詢請(qǐng)求時(shí)根據(jù)查詢?nèi)罩?，得?萬查詢query，作為query集.

3)實(shí)驗(yàn)方式.通過腳本程序?qū)uery集定時(shí)請(qǐng)求系統(tǒng)，模擬用戶訪問，訪問數(shù)由實(shí)驗(yàn)進(jìn)行調(diào)節(jié).

4)查詢語法.分類索引建立后，需要額外產(chǎn)生類別屬性category，在應(yīng)用端識(shí)別出本次查詢的category，語法如:category=3＆＆query=”MP3”＆＆hit=10＆＆…，其含義為查詢類別3的merge節(jié)點(diǎn)，查詢?cè)~為MP3，用戶感興趣的前10條文檔信息等.

Search 1的merge層采用集中方式，索引按照文檔劃分;Search2進(jìn)行分類和動(dòng)態(tài)化處理，按照多個(gè)節(jié)點(diǎn)的非集中方式管理.由于索引結(jié)構(gòu)的不同，導(dǎo)致二者查詢方式很大差異，使得查詢速度相差較大.同時(shí)，實(shí)驗(yàn)將要驗(yàn)證并行查詢算法對(duì)高并發(fā)任務(wù)的有效性.

3.1 merge層負(fù)載

為了驗(yàn)證改進(jìn)的模型結(jié)構(gòu)，在不同并發(fā)請(qǐng)求情況下，對(duì)Search1和Search2兩種結(jié)構(gòu)的merge層負(fù)載進(jìn)行試驗(yàn).圖8和圖9分別記錄多個(gè)并發(fā)query的merge層節(jié)點(diǎn)的CPU和內(nèi)存平均開銷，實(shí)驗(yàn)中設(shè)置返回用戶Top 100個(gè)結(jié)果，隨著請(qǐng)求并發(fā)數(shù)增多，內(nèi)存和CPU變化明顯.CPU開銷與并發(fā)數(shù)幾乎是線性增大，Search2的merge節(jié)點(diǎn)CPU占用率約為Search1的75%.merge層節(jié)點(diǎn)的內(nèi)存開銷主要對(duì)所屬類別索引節(jié)點(diǎn)的查詢中間結(jié)果的緩存，并發(fā)任務(wù)越多，Search1和Search2之間的內(nèi)存開銷相差越大，其原因是未分類Search1使得各個(gè)索引節(jié)點(diǎn)返回結(jié)果數(shù)以索引節(jié)點(diǎn)數(shù)的倍數(shù)增大，花費(fèi)更多內(nèi)存開銷.

圖9 Search1和Search2在不同并發(fā)數(shù)query的平均內(nèi)存占用率

由于傳統(tǒng)分布式模型對(duì)各個(gè)索引節(jié)點(diǎn)查詢結(jié)果需要進(jìn)行多次合并、排序等工作，使得merge成為系統(tǒng)的瓶頸，query的并發(fā)數(shù)直接影響merge節(jié)點(diǎn)性能;而改進(jìn)分布式模型根據(jù)索引類別，按照各類查詢的merge節(jié)點(diǎn)處理查詢信息，具有很強(qiáng)的針對(duì)性，從而減少merge節(jié)點(diǎn)的負(fù)載.

3.2 搜索節(jié)點(diǎn)的并行查詢性能

為了驗(yàn)證MMSH算法優(yōu)越性，實(shí)驗(yàn)中采用Search2模型.由于在倒排表索引不能完全存入內(nèi)存情況下，TAAT算法不需要磁盤訪問，優(yōu)勢(shì)高于DAAT算法，而文中實(shí)驗(yàn)側(cè)重討論此種情況下MMSH算法優(yōu)勢(shì)，為此MMSH算法只與TAAT算法進(jìn)行比較.在相同的并發(fā)用戶請(qǐng)求和多線程執(zhí)行下，從搜索引擎層的平均搜索時(shí)間和吞吐量兩個(gè)方面比較二者性能.實(shí)驗(yàn)中兩個(gè)重要參數(shù)是:線程數(shù)p和參數(shù)Top k(用戶選取前k個(gè)結(jié)果，k=10是系統(tǒng)默認(rèn)值).

圖10中，通過比較MMSH算法和TAAT算法的平均查找時(shí)間可以看出，MMSH算法具有明顯的優(yōu)勢(shì)，從圖10可以看出，多線程體現(xiàn)并行查詢的優(yōu)越性，平均查找時(shí)間幾乎隨著線程數(shù)目增大，下降趨勢(shì)明顯.當(dāng)線程數(shù)達(dá)到一定數(shù)量時(shí)，線程本身存在開銷，如繼續(xù)開啟更多線程，會(huì)降低系統(tǒng)性能，如實(shí)驗(yàn)中開啟64個(gè)線程效果沒有32線程好.這是由于在搜索過程中，改進(jìn)算法中利用MaxScore排除不必要計(jì)算過程，從而提高了查詢速度.

圖11的系統(tǒng)吞吐量是指整個(gè)搜索引擎層平均每秒鐘所能夠處理的merge層發(fā)送的請(qǐng)求數(shù)，而不是單個(gè)引擎的吞吐量.對(duì)于merge層發(fā)送的每一類請(qǐng)求，需要多個(gè)搜索節(jié)點(diǎn)并行搜索，然后把各種結(jié)果匯總到對(duì)應(yīng)的merge節(jié)點(diǎn).從圖9可以看出，在線程數(shù)達(dá)到32前，多線程技術(shù)幾乎能夠得到線性的加速比;TAAT算法在吞吐量方面落后于MMSH算法，體現(xiàn)了MMSH算法優(yōu)越性.線程數(shù)為32時(shí)，MMSH算法和TAAT算法的性能優(yōu)于64個(gè)線程數(shù)情況，這是由于過多的線程數(shù)導(dǎo)致線程開啟和切換的開銷較大.

圖10 搜索引擎層使用TAAT算法和MMSH算法平均查詢時(shí)間

圖11 搜索引擎層使用TAAT算法和MMSH算法時(shí)系統(tǒng)吞吐量

從圖10、11的Top k，可以看出啟動(dòng)相同的線程數(shù)目，k越大，查詢時(shí)間越長，吞吐量越小，并且MMSH算法優(yōu)于TAAT算法，即系統(tǒng)開銷越大.這是因?yàn)橛脩鬞op k中的k選擇，直接影響查詢過程中待計(jì)算的文檔得分?jǐn)?shù)量，導(dǎo)致系統(tǒng)性能差異.由于MMSH算法使用maxscore的提前打分策略，同等條件下，可以提高系統(tǒng)性能.

4 結(jié)論

1)根據(jù)文檔主題特征，對(duì)索引進(jìn)行分類，設(shè)計(jì)分類查詢方法，解決查詢盲目性.

2)對(duì)較長倒排記錄表設(shè)計(jì)Bitmap結(jié)構(gòu)，有效降低倒排表合并的查詢時(shí)間復(fù)雜度，實(shí)現(xiàn)快速的倒排合并工作.

3)利用maxscore策略和多線程方法，在查詢過程中建立詞項(xiàng)堆、結(jié)果堆和Bitmapmerge結(jié)構(gòu)，能夠提前結(jié)束查詢打分，從而優(yōu)化了倒排表查詢算法.

［1］HEINZ S，ZOBEL J.Efficient single-pass index construction for text databases［J］.Journal of the American Society for Information Science and Technology，2003，54(8):713-729.

［2］BüTTCHER S，CLARKE C L A.Indexing time vs.Query time trade-offs in dynamic information retrieval systems［C］//Proceedings of the 14th ACM International Conference on Information and Knowledge Management.New York，NY:ACM，2005:317-318.

［3］HAO Y，SHUAID，TORSTEN S.Inverted index compression and query processing with optimized document ordering［C］//Proceedings of the 18th International Conference on World Wide Web.New York，NY:ACM，2009:401-410.

［4］MANNING C D，RAGHAVAN P，SCHüTZE H.An introduction to information retrieval［M］.New York，NY:Cambridge University Press，2009:124-136.

［5］BüTTCHER S，CLARKE C L A，CORMACK G V.Information retrieval implementing and evaluating search engine［M］.Cambridge，MA:MIT Press，2010:137-173.

［6］TURTLE H，TOMPA F W.Query-evaluation:strategies and optimization［J］. Information Proceeding ＆Mangagement，1995，31(1):831-850.

［7］STROHMAN T，TURTLE H，CROFT W B.Optimization strategies for complex queries［C］//Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York，NY:ACM，2005:219-225.

［8］BARROSO L A，DEAN J，HOLZLE U.Web search for a planet:the google cluster architecture［J］.IEEE Micro，2003，23(2):22-28.

［9］王曉春，李生，楊沐昀，等.查詢會(huì)話中的用戶行為分析［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2011，43(5):76-78.

［10］靳巖欽，張敏，劉奕群，等.搜索引擎用戶查詢的廣告點(diǎn)擊意圖分析［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2013，45(1):124-128.

［11］黎玲利，王宏志，高宏，等.XML數(shù)據(jù)流上Top-K關(guān)鍵字查詢處理［J］.軟件學(xué)報(bào)，2012，114(4):1561-1577.

［12］李曉明，閆宏飛，王繼民.搜索引擎——原理、技術(shù)與系統(tǒng)［M］.2版.北京:科學(xué)出版社，2012:253-282.

［13］易明.基于 Web挖掘的個(gè)性化信息推薦［M］.北京:科學(xué)出版社，2010:93-110.

［14］STROHMAN T，CROFT W B.Efficient document retrieval in main memory［C］//Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York，NY:ACM，2007:175-182.

［15］ROBERSTON S，ZARAGOZA H，TAYLOR M.Simple BM25 extension to multiple weight fields［C］//Proceedings of the Thirteenth ACM International Coference on Information and Knowledge Management.New York，NT:ACM，2004:42-49.