基于閾值的快速啟動(dòng)Top-k查詢處理算法

江 宇，宋省身，楊岳湘，姜 琨

(1. 西北核技術(shù)研究所，陜西 西安 710024；2. 國防科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)學(xué)院，湖南 長沙 410073；3. 國防科學(xué)技術(shù)大學(xué) 信息中心，湖南 長沙 410073；4. 西安交通大學(xué) 電信學(xué)院，陜西 西安 710049)

基于閾值的快速啟動(dòng)Top-k查詢處理算法

江 宇1,2，宋省身2，楊岳湘3，姜 琨4

(1. 西北核技術(shù)研究所，陜西 西安 710024；2. 國防科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)學(xué)院，湖南 長沙 410073；3. 國防科學(xué)技術(shù)大學(xué) 信息中心，湖南 長沙 410073；4. 西安交通大學(xué) 電信學(xué)院，陜西 西安 710049)

Top-k查詢是搜索引擎領(lǐng)域廣泛應(yīng)用的技術(shù)之一，該算法從海量數(shù)據(jù)中返回最符合用戶需求的前k個(gè)結(jié)果,在執(zhí)行時(shí)能避免對(duì)大部分無關(guān)文檔的打分處理。Top-k 查詢雖然極大提升了查詢性能，但其存在的慢啟動(dòng)問題并未得到有效解決。為此，該文首先提取倒排索引的靜態(tài)Top-k信息，再動(dòng)態(tài)計(jì)算針對(duì)具體查詢?cè)~項(xiàng)的初始閾值，在此基礎(chǔ)上，結(jié)合MaxScore和WAND算法，提出了快速啟動(dòng)的Top-k查詢處理算法。實(shí)驗(yàn)結(jié)果表明，該方法能夠有效解決上述問題，具有良好的性能。

Top-k 查詢處理；閾值計(jì)算；倒排索引

1 引言

對(duì)索引文檔進(jìn)行查詢排名是信息檢索系統(tǒng)最主要的核心任務(wù)。目前大型搜索引擎擁有的網(wǎng)頁數(shù)據(jù)已達(dá)PB級(jí)別且每日處理成千上萬的查詢請(qǐng)求，使得系統(tǒng)在查詢處理過程中耗費(fèi)大量時(shí)間。因此，近年來針對(duì)查詢處理優(yōu)化的相關(guān)研究得到了商業(yè)界和學(xué)術(shù)界的重點(diǎn)關(guān)注。

盡管當(dāng)前搜索引擎都采用基于各類特征值的排序方法，但對(duì)所有候選結(jié)果都進(jìn)行如此復(fù)雜的計(jì)算顯然代價(jià)過大。通常，系統(tǒng)會(huì)先使用例如BM25等相對(duì)簡(jiǎn)單的檢索模型選出小部分可能進(jìn)入最終結(jié)果集的文檔，再在后續(xù)階段中引入特征值計(jì)算這些文檔的分?jǐn)?shù)。在此過程中，Top-k查詢處理方法是普遍采用的技術(shù)之一。Top-k查詢處理又稱提前停止或動(dòng)態(tài)剪枝技術(shù)，目的是在評(píng)估少量候選文檔的前提下，試圖找出與查詢?cè)~最相關(guān)的前k個(gè)結(jié)果。Top-k查詢處理技術(shù)避免了對(duì)所有文檔的檢查打分，極大地提高了搜索引擎的效率。

在前人提出的多種Top-k查詢算法中，最為經(jīng)典的是基于DAAT的MaxScore算法[1]和WAND算法[2]。這兩種算法使用跳躍訪問倒排鏈表和部分打分的方式，減少了窮盡遍歷算法90%以上的查詢開銷。自提出以來，研究人員[3-5]主要結(jié)合索引結(jié)構(gòu)、文檔估分方式和遍歷策略等方面對(duì)算法進(jìn)行了改進(jìn)和優(yōu)化，但其存在的“慢啟動(dòng)”問題一直沒有得到有效解決。“慢啟動(dòng)”問題，即在查詢剛開始時(shí)，對(duì)倒排鏈表的遍歷速度相對(duì)較慢，隨著查詢過程的進(jìn)行閾值才會(huì)逐漸增大，從而加快查詢處理速度。

為了解決這個(gè)問題，本文圍繞初始閾值的設(shè)置方法展開研究，在保證算法安全性的前提下，對(duì)MaxScore和WAND算法進(jìn)行相關(guān)優(yōu)化，提出了快速啟動(dòng)的MaxScore算法(rapid start MaxScore, RS-MaxScore)和WAND算法(rapid start WAND, RS-WAND)，并在TREC GOV2數(shù)據(jù)集上對(duì)這兩種算法進(jìn)行了實(shí)現(xiàn)和驗(yàn)證。

本文第二節(jié)介紹MaxScore和WAND算法的相關(guān)工作；第三節(jié)介紹快速啟動(dòng)的Top-k查詢處理算法RS-MaxScore和RS-WAND；第四節(jié)給出本文的相關(guān)實(shí)驗(yàn)結(jié)果及結(jié)果分析；第五節(jié)總結(jié)全文并提出未來工作。

2 相關(guān)工作

在搜索引擎和信息檢索領(lǐng)域中，根據(jù)對(duì)倒排鏈表的遍歷方式，大體可分為以下兩類查詢處理策略： Term-At-A-Time(TAAT)和Document-At-A-Time(DAAT)[6]。TAAT每次只打開一個(gè)查詢?cè)~項(xiàng)對(duì)應(yīng)的倒排鏈，然后對(duì)其進(jìn)行完整的遍歷，并對(duì)所有在倒排鏈中出現(xiàn)的文檔的評(píng)分進(jìn)行累加。DAAT則同時(shí)打開所有查詢?cè)~項(xiàng)的倒排鏈，在并行遍歷倒排鏈的過程中，每次對(duì)一個(gè)文檔進(jìn)行完整打分。DAAT在大規(guī)模數(shù)據(jù)集的良好性能，使得研究人員提出了多種基于DAAT的 Top-k查詢算法。目前，大型搜索引擎普遍采用的是MaxScore和 WAND。

2.1.1 MaxScore

MaxScore算法對(duì)每個(gè)查詢?cè)~項(xiàng)的倒排鏈保留一個(gè)指向當(dāng)前倒排項(xiàng)的指針，同時(shí)儲(chǔ)存每個(gè)倒排鏈的最大分?jǐn)?shù)，并將鏈表分為必要和非必要兩類。假設(shè)當(dāng)前Top-k的閾值為θ，首先將倒排鏈按最大分?jǐn)?shù)從大到小排序并對(duì)最大分?jǐn)?shù)進(jìn)行累加，如果累加分?jǐn)?shù)小于θ，則稱這些倒排鏈為非必要鏈表，反之其他的倒排鏈稱為必要鏈表。由于只有至少包含一個(gè)必要詞項(xiàng)的文檔才有可能進(jìn)入Top-k，我們便可以通過對(duì)必要鏈表中的文檔進(jìn)行打分來得到最后結(jié)果。從必要鏈表中文檔編號(hào)(docID)最小的文檔開始作為候選文檔，按順序進(jìn)行局部打分，即首先計(jì)算候選文檔在必要鏈表中的總分?jǐn)?shù)，如果該分?jǐn)?shù)加上非必要鏈表的最大累加分?jǐn)?shù)仍小于θ，即可終止打分；否則繼續(xù)累加該文檔在非必要鏈表中的分?jǐn)?shù)，直到得到完整打分或者在累加過程中提前終止。

圖1給出了MaxScore算法在查詢過程中的例子。圖中圓圈表示倒排鏈的當(dāng)前指針，圓圈中的數(shù)字表示當(dāng)前指針指向文檔的文檔號(hào)。按照倒排鏈最大分?jǐn)?shù)排序后，該查詢的4個(gè)倒排鏈為{green,blue,red,yellow}，它們的最大分?jǐn)?shù)分別為11、7、4、2，而此時(shí)最大分?jǐn)?shù)累加數(shù)組的值為20、13、6、2。若當(dāng)前閾值θ=8，則必要鏈表T={green,blue}，選取T中文檔號(hào)最小的文檔56為候選文檔。首先對(duì)blue打分，假設(shè)此時(shí)有兩種情況： ①blue的分?jǐn)?shù)為5。繼續(xù)對(duì)red進(jìn)行打分，在red中跳過56之前的文檔向后查找，結(jié)果并未找到56故red分?jǐn)?shù)為0。而此時(shí)56號(hào)文檔的真實(shí)分?jǐn)?shù)5加上yellow的最大分?jǐn)?shù)2為7，小于當(dāng)前閾值，因此不需要再對(duì)yellow進(jìn)行打分，即提前結(jié)束打分過程，重新選取下一個(gè)候選文檔；②blue的分?jǐn)?shù)為6。對(duì)red進(jìn)行同①的處理之后，繼續(xù)對(duì)yellow進(jìn)行打分，當(dāng)前指針從7號(hào)文檔跳躍到56號(hào)文檔，計(jì)算得到的分?jǐn)?shù)與6相加，若大于當(dāng)前閾值8，則將56號(hào)文檔插入結(jié)果堆中并更新閾值；若小于當(dāng)前閾值，則重新選擇候選文檔。

圖1 MaxScore算法示例

2.1.2 WAND

WAND算法同樣需要預(yù)先計(jì)算并儲(chǔ)存每個(gè)倒排鏈的最大分?jǐn)?shù)。該算法主要有三個(gè)步驟： ①選擇支點(diǎn)。首先按照各倒排鏈當(dāng)前指針指向的docID的升序?qū)Φ古沛溸M(jìn)行排列，再依次對(duì)倒排鏈的最大分?jǐn)?shù)進(jìn)行累加，當(dāng)累加分?jǐn)?shù)首次大于或等于當(dāng)前Top-k的閾值θ時(shí)，最后一個(gè)參與累加的倒排鏈對(duì)應(yīng)的詞項(xiàng)即為支點(diǎn)詞，其當(dāng)前指針指向的docID為支點(diǎn)ID。②檢查對(duì)齊。即以docID為準(zhǔn)，對(duì)所有排列在支點(diǎn)詞之前的詞項(xiàng)進(jìn)行對(duì)齊——使倒排鏈的指針移動(dòng)到docID大于或等于支點(diǎn)ID的倒排項(xiàng)上，如果返回的結(jié)果中有docID大于支點(diǎn)ID，則回到第一步對(duì)所有倒排鏈再次排序并重新選擇支點(diǎn)詞；如果所有返回結(jié)果都等于支點(diǎn)ID，則docID為支點(diǎn)ID的文檔為候選文檔，進(jìn)行第三步。③對(duì)候選文檔進(jìn)行完整打分，用以判斷其是否能夠真正進(jìn)入Top-k，然后將所有指針向前移動(dòng)一步。

圖2為WAND算法在查詢過程中選擇支點(diǎn)的例子。按照當(dāng)前文檔號(hào)從小到大排序后，該查詢的4個(gè)倒排鏈為{blue,red,green,yellow}，它們的最大分?jǐn)?shù)分別為7、4、11、2。假設(shè)當(dāng)前閾值θ=20，則最大分?jǐn)?shù)累加到green時(shí)分?jǐn)?shù)首次大于閾值(7+4+11gt;20)，此時(shí)green為支點(diǎn)詞，56為支點(diǎn)ID。此時(shí)應(yīng)對(duì)blue和red兩個(gè)倒排鏈進(jìn)行對(duì)齊，若對(duì)齊成功即兩個(gè)倒排鏈的當(dāng)前文檔號(hào)都為56，則將56號(hào)文檔視為候選文檔，進(jìn)行完全打分，最后以文檔真實(shí)分?jǐn)?shù)判斷是否能夠插入結(jié)果堆。若對(duì)齊不成功，如圖2所示，blue的當(dāng)前文檔號(hào)為70，則對(duì)倒排鏈重新排序，變?yōu)閧red,green,blue,yellow}，重新選擇支點(diǎn)詞和支點(diǎn)ID。

圖2 WAND算法示例

從上可知，大體來講MaxScore和WAND的主要差別是對(duì)各倒排鏈表遍歷的順序不同。而共同之處在于它們都在查詢過程中維護(hù)一個(gè)大小為k的堆來保存當(dāng)前得分最多的k個(gè)文檔，并以堆中的最小分?jǐn)?shù)作為閾值。若新的文檔分?jǐn)?shù)可能大于閾值，則將其視作候選文檔，并進(jìn)行完全打分，當(dāng)完全打分后的分?jǐn)?shù)超過閾值，便將相應(yīng)文檔插入堆并更新閾值；反之，則放棄該文檔繼續(xù)遍歷倒排鏈表，直到所有鏈表均遍歷完成。由此，算法的優(yōu)勢(shì)在于避免對(duì)估分低于閾值的文檔進(jìn)行精確評(píng)分，使得查詢效率大幅提升。但是，在查詢剛開始時(shí)，堆中沒有文檔，初始閾值為0，任何文檔都能進(jìn)入堆中，而這些文檔很可能在后面的查詢中被相關(guān)度更高的文檔淘汰。實(shí)際上，在開始查詢的一段時(shí)間里，過低的閾值并沒有起到很好的“過濾”作用，使大量相關(guān)度小的文檔的處理耗費(fèi)太多時(shí)間。隨著查詢處理的進(jìn)行，閾值會(huì)逐漸變大，查詢處理速度將明顯變快，這就是上述算法的慢啟動(dòng)問題。由此可見，將初始閾值設(shè)置為某個(gè)大于0的值可以加快查詢處理過程，并且當(dāng)初始閾值大小等于查詢結(jié)束時(shí)堆的最終閾值(即結(jié)果集的最小分?jǐn)?shù))，將取得最好的加速效果。

Broder等人[2]在提出WAND算法時(shí)便對(duì)閾值設(shè)置進(jìn)行了討論，但只對(duì)合取查詢的非零初始閾值給出了優(yōu)化方案，但對(duì)于應(yīng)用更廣的析取查詢沒有深入研究；Strohman等人[7]和Rossi等人[8]在分別改進(jìn)MaxScore和WAND時(shí)使用多層索引保存一定比例的高分?jǐn)?shù)文檔，計(jì)算這些文檔分?jǐn)?shù)并使用最小分?jǐn)?shù)作為初始閾值，對(duì)提高查詢效率有明顯效果，但與最優(yōu)值相比還有一定差距。Ding 和Suel在[9]中將初始閾值的估算作為開放性問題，證明當(dāng)初始閾值與最終閾值相等時(shí)，WAND的查詢時(shí)間將縮短20%，雖具有指導(dǎo)意義，但并未對(duì)計(jì)算方法展開討論。Carvalho等人[10]提出了一種啟發(fā)式BMW算法，以查詢?cè)~對(duì)應(yīng)倒排鏈中排名第k的部分分?jǐn)?shù)作為初始閾值，使查詢處理過程有所加快，但這種估算方式依舊不夠準(zhǔn)確。

結(jié)合前人的工作，本文繼續(xù)對(duì)慢啟動(dòng)問題的解決方案進(jìn)行探討，提出了一種既保證算法安全性，又更加接近最優(yōu)值的計(jì)算方法，并在TREC GOV2數(shù)據(jù)集上對(duì)該方法進(jìn)行了實(shí)現(xiàn)和驗(yàn)證。

3 快速啟動(dòng)的Top-k查詢處理算法

3.1 基本思想

初始閾值的計(jì)算涉及兩個(gè)問題： ①如何保證算法的安全性；②如何設(shè)置這個(gè)非零值，使慢啟動(dòng)問題能有效解決。Top-k查詢算法的安全性，是指使用該算法所得到的結(jié)果和使用窮盡查詢算法得到的結(jié)果是完全相同的，這里的“相同”包括三個(gè)方面： 相同的文檔、相同的排序和相同的分?jǐn)?shù)。可以看出，上述兩個(gè)問題是相互矛盾的。從解決慢啟動(dòng)問題的角度看，過小的初始閾值起不到很好的加速效果，故其值應(yīng)當(dāng)越大越好。但另一方面，過大的初始閾值將使查詢變得不安全。顯然，當(dāng)其值大于結(jié)果集的最小分?jǐn)?shù)時(shí)，部分本應(yīng)進(jìn)入最終結(jié)果的文檔將會(huì)被“丟棄”。實(shí)際上，結(jié)果集的最小分?jǐn)?shù)RS正是初始閾值的最優(yōu)解。但這個(gè)最優(yōu)解在查詢處理過程完成后才能得到，事先無法進(jìn)行預(yù)測(cè)或計(jì)算，所以研究人員都致力于讓初始閾值盡可能接近該值。

為了更好地估算初始閾值，本文首先在索引階段提取出每個(gè)倒排鏈分?jǐn)?shù)排名前k的k個(gè)倒排項(xiàng)，作為靜態(tài)信息將其儲(chǔ)存在toplist結(jié)構(gòu)當(dāng)中。對(duì)于給定的查詢，先對(duì)查詢?cè)~對(duì)應(yīng)倒排鏈的toplist中的文檔進(jìn)行完全打分，然后把分?jǐn)?shù)按從大到小的順序進(jìn)行排列，最后以第k個(gè)分?jǐn)?shù)TS作為初始閾值。

證:令

Sk={sx∈S|sxgt;sk-1,0lt;k≤n},

綜上，按照上述方法計(jì)算的初始閾值不會(huì)“丟棄”原本最終排名能夠進(jìn)入前k的文檔，保證了算法的安全性。并且當(dāng)查詢?cè)~對(duì)應(yīng)倒排鏈的toplist重合文檔數(shù)量越多，TS越接近最優(yōu)解RS；在極端情況下，若toplist文檔完全相同，計(jì)算得到值等于RS。

3.2 RS-MaxScore和RS-WAND算法

本文將上節(jié)所述的初始閾值計(jì)算方法與現(xiàn)有兩個(gè)經(jīng)典Top-k查詢算法MaxScore和 WAND相結(jié)合，得到RS-MaxScore算法(偽代碼見算法1)和RS-WAND算法(偽代碼見算法2)。

算法1RS-MaxScore算法

1.RS-MaxScore(queryTerms[0...q-1] ,k)

2. I[]=getIterators[0...q-1], termID[]=getTermID[0...q-1], numTerms=q,numReqTerms=q; //I為倒排鏈遍歷器

3. initReqScore=calcThreshold (termID[0...q-1]); //計(jì)算初始閾值

4. reqScore=initReqScore;

5. 計(jì)算最大分?jǐn)?shù)累加數(shù)組accScores[0...q-1];

6. loop:whilenumReqTermsgt;0do

7.fori=0;ilt;numReqTerms;i=i+1do

8.ifI[i].doc==lastdocthen

9. 刪除I[i], 更新accScores[], numTerms--, numReqTerms--;

10.whilenumReqTermsgt;0andaccScores[numReqTerms-1] lt; reqScoredo

11. numReqTerms--;

12.ifnumReqTerms lt;= 0then

13. break loop;

14. 選擇I[0...numReqTerms]中的最小當(dāng)前文檔號(hào)為canddoc; //candoc為候選文檔號(hào)

15. score=0;

16.fori = 0; i lt; numTerms and score + accScores[i] gt;= reqScore; i=i+1do

17.ifigt;=numReqTerms and Ii.skipTo(canddoc) == -1then//跳到大于等于候選文檔號(hào)

18. 刪除I[i], 更新accScores[], numTerms--;

19.elseifIi.doc == canddocthen//計(jì)算候選文檔分?jǐn)?shù)

20. score +=I[i].score;

21.ifscore lt; reqScorethen

22. continue;

23.else//候選文檔分?jǐn)?shù)大于閾值

24. rheap.insert(canddoc, score); //插入結(jié)果堆

25.ifrheap.minScore()gt;initReqScorethen

26. reqScore = rheap.minScore(); //當(dāng)結(jié)果堆最小分?jǐn)?shù)大于初始閾值時(shí)，更新閾值

27.whilenumReqTerms gt; 0 and accScores[numReqTerms-1] lt; reqScoredo

28. numReqTerms--;

29.returnrheap.result();

算法2RS-WAND算法

1.RS-WAND(queryTerms[0...q-1] ,k)

2. I[]=getIterators[0...q-1], termID[]=getTermID[0...q-1], numTerms=q;

3. initReqScore=calcThreshold (termID[0...q-1]);

4. reqScore=initReqScore;

5. loop:whilenumTermsgt;0do

6. sort(I[0...numTerms-1]);

7. tempScore=0,pivot=0;

8.fori = 0; i lt; numTerms; i=i+1do

9. tempScore+=I[i].maxScore;

10.iftmpaccScoregt;=reqScorethen

11. pivotdoc=I[i].doc;

12.forj = i-1; j gt;=0; j=j-1do

13. I[j].skipTo(pivotdoc);

14.ifI[j].doc() gt; pivotdocthen

15.continueloop;

16. canddoc = pivotdoc;

17. 檢查倒排鏈?zhǔn)欠癖闅v完成，若完成，則刪除對(duì)應(yīng)遍歷器，更新I[],numTerms--;

18.ifnumTerms==0then

19.break;

20. 對(duì)文檔進(jìn)行完全打分，得到文檔分?jǐn)?shù)score;

21.ifscore lt; reqScorethen

22.continue;

23.else//候選文檔分?jǐn)?shù)大于閾值

24. rheap.insert(canddoc, score); //插入結(jié)果堆

25.ifrheap.minScore()gt;initReqScorethen

26. reqScore = rheap.minScore(); //當(dāng)結(jié)果堆最小分?jǐn)?shù)大于初始閾值時(shí)，更新閾值

27.returnrheap.result();

從上可知，RS-MaxScore算法和RS-WAND算法與原算法最主要的區(qū)別是在進(jìn)行倒排鏈遍歷前，首先提取查詢?cè)~ID，再利用toplists中的靜態(tài)信息調(diào)用calcThreshold ()(見算法3)對(duì)初始閾值進(jìn)行計(jì)算。當(dāng)有新結(jié)果插入堆后，需要判斷堆的最小分?jǐn)?shù)是否大于初始閾值，否則不更新堆的當(dāng)前閾值。

算法3 calcThreshold (termID[])

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)環(huán)境

本文使用未壓縮的TREC GOV2數(shù)據(jù)集作為測(cè)試集，它包含2 500萬個(gè)網(wǎng)頁，數(shù)據(jù)規(guī)模為426GB。查詢語句從Terabyte Track 05 Efficiency查詢集中按需求隨機(jī)選取1 000條，作為實(shí)驗(yàn)查詢輸入。索引采用與文獻(xiàn)[11]相類似的多層自索引結(jié)構(gòu)，能夠?qū)Φ古沛溸M(jìn)行隨機(jī)訪問。其中，每128個(gè)文檔號(hào)和詞頻為一個(gè)塊進(jìn)行壓縮，壓縮算法為NewPFD。系統(tǒng)檢索模型為Okapi BM25。

系統(tǒng)由Java實(shí)現(xiàn)，JDK版本為1.7。測(cè)試平臺(tái)硬件配置為： IntelI CoreI i5處理器，3.20 GHz主頻，12 GB內(nèi)存。

4.2 實(shí)驗(yàn)結(jié)果與分析

4.2.1 性能指標(biāo)

表1至表3分別展示了RS-MaxScore與RS-WAND算法在不同k值和查詢?cè)~長度下，插入堆文檔數(shù)(Heap inserted)、文檔打分次數(shù)(Documents scored)、讀入磁盤數(shù)據(jù)塊數(shù)量(Blocks read)三項(xiàng)主要性能指標(biāo)，以及與原算法相比取得的性能提升。其中，L表示查詢?cè)~長度，%I表示性能提升的百分比，H表示每個(gè)查詢插入堆的平均文檔數(shù)，D表示每個(gè)查詢平均打分次數(shù)，B表示每個(gè)查詢平均讀入磁盤數(shù)據(jù)塊數(shù)量。

從表1可以看出，RS-MaxScore與RS-WAND算法能夠有效減少查詢處理時(shí)插入堆的文檔數(shù)，這得益于非零初始閾值的“過濾”效果。當(dāng)k固定時(shí)，減少文檔數(shù)的效果隨著L的增大而降低。這是因?yàn)長的增大將導(dǎo)致初始閾值計(jì)算階段估算的文檔增多，使得到的閾值更加偏離最優(yōu)解。而當(dāng)L固定時(shí)，減少文檔數(shù)的效果隨著k的增大而提升。這是由于在原算法中，k值越大，查詞處理初始階段進(jìn)入堆的無效文檔越多，使得改進(jìn)的算法“過濾”的文檔相對(duì)更多。從表2可以看到，在文檔打分次數(shù)方面，RS-MaxScore與RS-WAND算法有一定的提升，通過避免對(duì)部分文檔完全打分加快了查詢處理過程。同時(shí)應(yīng)該看到，表3指出在大部分情況下，讀入磁盤數(shù)據(jù)塊的數(shù)量在算法改進(jìn)后略微減少，這是因?yàn)樘岢龅膬煞N算法仍需對(duì)可能進(jìn)入結(jié)果堆的文檔進(jìn)行部分打分評(píng)估，從而在讀磁盤操作上并不會(huì)有明顯提升。

表1 RS-MaxScore與RS-WAND算法的插入堆文檔數(shù)(H)及其性能提升(%I)

注：L為查詢?cè)~長度

表2 RS-MaxScore與RS-WAND算法的文檔打分次數(shù)(D)及其性能提升(%I)

注： L為查詢?cè)~長度

表3 RS-MaxScore與RS-WAND算法讀入磁盤數(shù)據(jù)塊的數(shù)量(D)及其性能提升(%I)

注：L為查詢?cè)~長度

4.2.2 不同k值對(duì)查詢執(zhí)行時(shí)間的影響

圖3展示了在不同k值下，MaxScore、RS-MaxScore及RSM-Opt(optimal rapid start MaxScore)三種算法的執(zhí)行時(shí)間，其中查詢?cè)~長度采用隨機(jī)選取的方式。RSM-Opt是指初始閾值設(shè)置為最優(yōu)解的快速啟動(dòng)算法，在預(yù)處理階段對(duì)固定查詢集進(jìn)行第一次處理，記錄每條查詢結(jié)果集的最小分?jǐn)?shù)后，在正式查詢階段使用記錄好的分?jǐn)?shù)作為初始閾值，并使用MaxScore算法對(duì)相同查詢集進(jìn)行第二次處理。該算法不具有實(shí)際應(yīng)用意義，但其查詢執(zhí)行時(shí)間在理論上為基于閾值計(jì)算的改進(jìn)方式,能夠達(dá)到的最短時(shí)間，具有參照價(jià)值。當(dāng)k=1時(shí)，RS-MaxScore與RSM-Opt的初始閾值相同，但由于前者需要對(duì)初始閾值進(jìn)行計(jì)算，故查詢執(zhí)行時(shí)間略長于后者。當(dāng)k增大時(shí)，三種算法執(zhí)行時(shí)間都隨之增長，這是因?yàn)榉祷亟Y(jié)果數(shù)量的增加意味著結(jié)果集文檔得分閾值的下降，使得評(píng)估文檔數(shù)增多。在k分別為10、20、50時(shí)，RS-MaxScore對(duì)原算法的速度提升分別為15.6%、21%、16.7%。

圖3 不同k值下MaxScore、RS-MaxScore和RSM-Opt的 平均查詢執(zhí)行時(shí)間

圖4展示了在不同k值下，WAND、RS-WAND及RSW-Opt(optimal rapid start WAND)三種算法的執(zhí)行時(shí)間。與RSM-Opt相似，RSW-Opt也是初始閾值設(shè)置為最優(yōu)解的快速啟動(dòng)算法，具有參考價(jià)值，所不同的是其正式查詢階段使用的是WAND算法?？梢钥吹剑c圖1相比RS-WAND的時(shí)間折線更接近于原算法，說明快速啟動(dòng)的策略對(duì)MaxScore來說更加有效，這可能是因?yàn)镸axScore在查詢過程中并不改變?cè)~項(xiàng)鏈表順序，非零初始閾值能夠有效地劃分必要鏈表和非必要鏈表，使算法性能提升更高。但即使如此，RS-WAND對(duì)原算法的速度提升也在5%～8%之間。

圖4 不同k值下WAND、RS-WAND和RSW-Opt的 平均查詢執(zhí)行時(shí)間

4.2.3 不同查詢?cè)~長度對(duì)查詢執(zhí)行時(shí)間的影響

圖5展示了在不同查詢?cè)~長度下各算法的查詢執(zhí)行時(shí)間，其中k=50。從圖中可以看出，MaxScore的執(zhí)行時(shí)間低于WAND，且RS-MaxScore的執(zhí)行時(shí)間低于RS-WAND。隨著查詢?cè)~長度L增大，四種算法的執(zhí)行時(shí)間都基本呈增長的趨勢(shì)。無論L取值多少，RS-MaxScore和RS-WAND的執(zhí)行時(shí)間都比原算法少并都在L=5時(shí)取得最佳的效率，分別為20.6%和11.8%。

圖5 不同查詢?cè)~長度下各算法的平均查詢執(zhí)行時(shí)間

5 結(jié)束語

本文針對(duì)Top-k查詢算法的慢啟動(dòng)問題，對(duì)每個(gè)查詢?cè)~倒排鏈的Top-k文檔進(jìn)行提取，以此為依據(jù)對(duì)算法的初始閾值進(jìn)行估算，結(jié)合現(xiàn)有的MaxScore和WAND算法，在保證安全性的前提下提出了RS-MaxScore和RS-WAND算法，實(shí)驗(yàn)證明，所提方案具有良好的性能。

未來將會(huì)在現(xiàn)有工作上進(jìn)行更多的優(yōu)化： 進(jìn)一步探索在估算閾值階段，合并后的文檔數(shù)量與原文檔數(shù)量的比值，估算閾值與最優(yōu)閾值的比值之間的關(guān)系，嘗試建立數(shù)學(xué)模型，從而方便有效地使初始閾值更接近于最優(yōu)閾值。

[1] Turtle H, Flood J. Query evaluation: strategies andoptimizations[J]. Information Processing amp; Management, 1995, 31(6): 831-850.

[2] Broder A Z, Carmel D,Herscovici M, et al. Efficient query evaluation using a two-level retrieval process[C]// Proceedings of the 12th International Conference on Information and Knowledge Management. ACM, 2003: 426-434.

[3] Moffat A,Zobel J. Self-indexing inverted files for fast text retrieval[J]. ACM Transactions on Information Systems (TOIS), 1996, 14(4): 349-379.

[4] Jonassen S, Bratsberg S E. Efficient compressed inverted index skipping for disjunctive text-queries[M]. Advances in Information Retrieval. Springer Berlin Heidelberg, 2011: 530-542.

[5] Yan H, Ding S,Suel T. Inverted index compression and query processing with optimized document ordering[C]//Proceedings of the 18th International Conference on World Wide Web. ACM, 2009: 401-410.

[6] Ricardo B Y, Berthier R N. Modern information retrieval: the concepts and technology behind search (2nd Edition)[M]. Addision Wesley, 2011, 84: 2.

[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. ACM, 2005: 219-225.

[8] Rossi C, de Moura E S,Carvalho A L, et al. Fast document-at-a-time query processing using two-tier indexes[C]//Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 2013: 183-192.

[9] Ding S,Suel T. Faster Top-k document retrieval using block-max indexes[C]//Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 2011: 993-1002.

[10] de Carvalho L L S, de Moura E S, Daoud C M, et al. Heuristics to improve the BMW method and its variants[J]. Journal of Information and Data Management, 2016, 6(3): 178.

[11] Jonassen S, Bratsberg S E. Efficient compressed inverted index skipping for disjunctive text-queries[M]. Advances in Information Retrieval. Springer Berlin Heidelberg, 2011: 530-542.

江宇(1987—)，碩士，工程師，主要研究領(lǐng)域?yàn)樾畔z索。

E-mail： jiangyu1406@163.com

宋省身(1990—)，博士研究生，主要研究領(lǐng)域?yàn)樾畔z索。

E-mail： songxingshen@nudt.edu.cn

楊岳湘(1967—)，博士，研究員，主要研究領(lǐng)域?yàn)樾畔z索。

E-mail： yyx@nudt.edu.cn

RapidStartTop-kQueryBasedonThreshold

JIANG Yu1,2, SONG Xingshen2, YANG Yuexiang3, JIANG Kun4

(1. Northwest Institute of Nuclear Technology, Xi’an, Shaanxi 710024, China；2. College of Computer, National University of Defense Technology, Changsha, Hunan 410073, China；3. Information Center, National University of Defense Technology, Changsha, Hunan 410073, China；4. School of Electronic and Information Engineering,Xi’an Jiaotong University, Xi’an, Shaanxi 710049, China)

Top-k query is a popular technique of search engines, which returns the most relative results for user from massive data. Although Top-k query significantly improves the performance of the system, its slow-start issue has not been effectively resolved. This paper extracts static Top-k information of inverted index and then calculats initial threshold in real time for specific query. On this basis, this paper presents a rapid start algorithm of Top-k query for the current state-of-art methods MaxScore and WAND. Experimental results show that the proposed approach achieves better performance.

Top-k query; threshold-calculation; inverted index

1003-0077(2017)05-0163-08

TP391

A

2016-08-16定稿日期2016-12-26

湖南省自然科學(xué)基金(2016JJ2007)