黃 達(dá)，閆宏飛

北京大學(xué) 信息科學(xué)技術(shù)學(xué)院，北京 100871

復(fù)雜布爾查詢下的文檔收集打分策略的優(yōu)化*

黃 達(dá)+，閆宏飛

北京大學(xué) 信息科學(xué)技術(shù)學(xué)院，北京 100871

HUANG Da,YAN Hongfei.Optimization for collecting and scoring documents for complex Boolean query. Journal of Frontiers of Computer Science and Technology,2017,11(1)：106-113.

雖然布爾查詢是信息檢索領(lǐng)域中較早提出的一個(gè)概念，但是對(duì)布爾查詢的大量研究主要還是針對(duì)布爾操作一致的布爾查詢。對(duì)于復(fù)雜布爾查詢，目前并沒(méi)有太多的相關(guān)研究，復(fù)雜布爾查詢卻越來(lái)越被頻繁地使用（如文本推薦領(lǐng)域）。為了促使這類查詢能夠被更加高效地執(zhí)行，提出了一種基于DAAT（document-at-a-time）框架的文檔收集打分策略——DCQ（DAAT for complex query）算法，并與著名開(kāi)源搜索引擎Lucene進(jìn)行比較實(shí)驗(yàn)，查詢性能有了顯著提升。此外，提出了一套對(duì)查詢性能的回歸預(yù)測(cè)機(jī)制，該機(jī)制能比較準(zhǔn)確地決策DCQ算法的使用時(shí)機(jī)。實(shí)驗(yàn)表明，結(jié)合了性能預(yù)測(cè)器的復(fù)合算法要遠(yuǎn)優(yōu)于Lucene當(dāng)前的文檔收集打分算法。

復(fù)雜布爾查詢；查詢優(yōu)化；性能回歸

1 引言

在信息檢索領(lǐng)域，所謂布爾查詢，是指在詞項(xiàng)上通過(guò)布爾邏輯操作符（與或非）構(gòu)建出布爾表達(dá)式，從而表達(dá)用戶希望文檔所具有的特征[1]。這種查詢語(yǔ)義精確，易于實(shí)現(xiàn)，因此早期搜索引擎的查詢模式都是以布爾查詢?yōu)橹?。盡管在加入了打分排序機(jī)制后，布爾查詢的檢索功能有了顯著提高[2]，但由于其查詢表達(dá)式較為繁瑣，而且對(duì)大多數(shù)用戶來(lái)說(shuō)，要用布爾表達(dá)式來(lái)精確定義檢索需求是非常困難的，從而在通用搜索領(lǐng)域，布爾查詢已經(jīng)被更加簡(jiǎn)單的關(guān)鍵詞查詢所替代[3]。

然而即便如此，憑借其精確和高效的特性，一方面，布爾查詢?nèi)匀粸楦鞔笏阉饕嫠Ａ?，人們?nèi)匀豢梢酝ㄟ^(guò)搜索引擎的高級(jí)搜索功能來(lái)定義布爾查詢（如百度[4]、谷歌[5]）。另一方面，關(guān)鍵詞查詢?cè)诤笈_(tái)進(jìn)行預(yù)處理時(shí)往往會(huì)根據(jù)查詢?nèi)罩?、同義詞表等數(shù)據(jù)結(jié)構(gòu)，轉(zhuǎn)換成極為復(fù)雜的布爾查詢表達(dá)式，在后臺(tái)發(fā)揮核心作用[6-7]。

此外，布爾查詢?cè)谝恍┟嫦蛱囟I(lǐng)域的搜索引擎中仍然處于主導(dǎo)地位[8]。比如，法律搜索[9]和專利搜索[10]，因?yàn)榉珊蛯＠臅?shū)的用詞有著高度的嚴(yán)謹(jǐn)性和專業(yè)性，使得精確的布爾查詢反而更容易滿足用戶的檢索需求。

在一些新興的研究領(lǐng)域，特別是社交推薦領(lǐng)域[11]，隨著數(shù)據(jù)規(guī)模的增大，對(duì)每個(gè)候選信息單元進(jìn)行打分顯然越來(lái)越不現(xiàn)實(shí)。因此，研究者們已經(jīng)開(kāi)始結(jié)合搜索引擎來(lái)制作推薦系統(tǒng)[12-13]。他們的框架往往是先利用用戶的個(gè)人信息提取出詞項(xiàng)，然后生成復(fù)雜的布爾查詢，進(jìn)而通過(guò)搜索引擎檢索出前K個(gè)相關(guān)文檔，再在這K個(gè)文檔上進(jìn)行細(xì)化打分。

由此可見(jiàn)布爾查詢?cè)谏鲜龈鲬?yīng)用場(chǎng)景下，查詢語(yǔ)句往往同時(shí)混合了多種布爾邏輯操作。然而，目前絕大多數(shù)搜索引擎的布爾查詢語(yǔ)法都是AND、OR、NOT和括號(hào)的組合，比如：((aANDb)ORcORd)AND NOTeAND NOTf，這種語(yǔ)法忽視了多種布爾操作混合在一起的優(yōu)化可能性。著名開(kāi)源搜索引擎Lucene（http://lucene.apache.org/）雖然可以用“+a+b c d-e-f”來(lái)表示上述查詢，但其內(nèi)部處理的方法仍然沒(méi)有考慮混合型的優(yōu)化。

針對(duì)這種情況，本文提出了一種針對(duì)復(fù)雜布爾查詢的基于DAAT（document-at-a-time）框架的文檔收集打分新策略——DCQ（DAAT for complex query）算法，該策略把復(fù)雜布爾查詢當(dāng)成一個(gè)整體來(lái)進(jìn)行優(yōu)化。本文以Lucene作為基準(zhǔn)程序（Baseline），以維基百科（http://en.wikipedia.org/）詞條作為數(shù)據(jù)集。通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，DCQ算法能在復(fù)雜布爾查詢下優(yōu)于基準(zhǔn)程序。另外，提出了一種高效的性能回歸預(yù)測(cè)機(jī)制，使得人們可以根據(jù)具體的查詢，決策DCQ算法的使用時(shí)機(jī)，進(jìn)而保證任何情況下查詢性能都不會(huì)下降。

本文探討了復(fù)雜布爾查詢下，文檔搜集和打分策略的優(yōu)化方法，并對(duì)該方法的性能進(jìn)行了深入分析，提出了一種性能回歸預(yù)測(cè)機(jī)制。本文組織結(jié)構(gòu)如下：第2章對(duì)復(fù)雜布爾查詢下的文檔收集打分問(wèn)題進(jìn)行分析，并提出DCQ算法；第3章研究DCQ算法的性能，并給出一種性能回歸預(yù)測(cè)機(jī)制；第4章介紹實(shí)驗(yàn)設(shè)置和實(shí)驗(yàn)結(jié)果；最后對(duì)全文進(jìn)行了總結(jié)。

2 問(wèn)題分析與方法描述

2.1 問(wèn)題描述

現(xiàn)有若干個(gè)待查詢的詞項(xiàng)：t11,t12,…,t1m,t21,t22,…,t2n,t31,t32,…,t3p，需要找到所有滿足下述條件的文檔d：

并對(duì)文檔d進(jìn)行打分，其分值為：

顯然，上述定義所描述的是一個(gè)典型的復(fù)雜布爾查詢。在該定義下：

（1）每一個(gè)被命中的文檔，必須包含所有的t1i，故稱每個(gè)t1i項(xiàng)為該查詢的MUST子句；

（2）每一個(gè)被命中的文檔，不得包含任意一個(gè)t2j，故稱每個(gè)t2j項(xiàng)為該查詢的MUST_NOT子句；

（3）是否包含t3k并不會(huì)對(duì)文檔的命中產(chǎn)生影響，但總體上看，包含的t3k項(xiàng)越多，文檔分值越高，故稱每個(gè)t3k項(xiàng)為該查詢的SHOULD子句。

為簡(jiǎn)潔起見(jiàn)，上述定義所描述的查詢符號(hào)化為q：

2.2 文檔收集打分策略分析

對(duì)所有命中文檔進(jìn)行收集打分的方法主要有兩種：每一步收集一個(gè)命中文檔的DAAT，以及每一步疊加一個(gè)倒排表（posting list）的TAAT（term-at-a-time）。

TAAT的優(yōu)點(diǎn)在于程序局部性較好，磁盤(pán)尋道時(shí)間較短，但其所占用的內(nèi)存空間較大；DAAT的優(yōu)點(diǎn)在于內(nèi)存占用較少，但其需要在倒排表之間進(jìn)行切換，以致程序局部性較差[14]。然而，跳表[15]和緩存技術(shù)的引入，使得DAAT在絕大多數(shù)情況下都要優(yōu)于TAAT。因此，Lucene使用DAAT作為其主要的文檔收集打分方法。

然而在過(guò)去的研究中，對(duì)文檔收集打分方法的研究?jī)H僅局限于“子句全與”(q=+t11+t12…+t1m)和“子句全或”(q=t31t32…t3p)，對(duì)于復(fù)雜布爾查詢下該如何對(duì)文檔進(jìn)行收集打分，并沒(méi)有很深入的研究。

Lucene處理查詢表達(dá)式（2）的現(xiàn)行做法是把它按照以下的查詢結(jié)構(gòu)來(lái)處理：

其含義是：用t11t12…t1m的合取式減去t21t22…t2n的析取式來(lái)得到結(jié)果集合，并對(duì)集合中的元素用t31t32…t3p的析取式的命中情況來(lái)加分。

顯然，在計(jì)算t21t22…t2n和t31t32…t3p的析取式的時(shí)候需要通過(guò)維護(hù)一個(gè)堆（heap）的結(jié)構(gòu)來(lái)求得每個(gè)命中文檔，這就需要分別花費(fèi)Θ(nlbn)和Θ(plbp)的時(shí)間開(kāi)銷。然而，這個(gè)開(kāi)銷實(shí)際上并不是完全必要的，因?yàn)槿藗冎魂P(guān)心t1i與t2j、t3k之間的關(guān)系，而不關(guān)心各t2j之間、各t3k之間的關(guān)系。上述提到的維護(hù)堆的操作實(shí)際上就是計(jì)算這些多余的人們不關(guān)心的信息。

2.3 DCQ算法

為了減少多余的堆調(diào)整開(kāi)銷，本文提出了DCQ算法。此算法是在DAAT的框架下同時(shí)處理查詢的所有子句，從而避免了用堆來(lái)維護(hù)t2j和t3k所產(chǎn)生的開(kāi)銷。其迭代器的next方法的具體實(shí)現(xiàn)如下所示。

3 性能分析和性能回歸預(yù)測(cè)

3.1 性能分析

假設(shè) +t11+t12…+t1m命中N個(gè)文檔，在最壞情況下Lucene每取一個(gè)文檔都要分別對(duì)MUST_NOT子句集和SHOULD子句集進(jìn)行堆調(diào)整，其時(shí)間復(fù)雜度為Θ(N(nlbn+plbp))；而對(duì)于DCQ算法，由于不需要進(jìn)行堆調(diào)整，其文檔收集打分的過(guò)程相當(dāng)于把命中文檔集掃描n+p遍，因此其時(shí)間復(fù)雜度為Θ(N(n+p))。

DCQ算法雖然在時(shí)間復(fù)雜度上要優(yōu)于Lucene，然而在實(shí)際使用的時(shí)候有兩個(gè)因素會(huì)導(dǎo)致DCQ算法慢于Lucene：

（1）DCQ算法需要同時(shí)處理多種不同邏輯連接的子句，其控制邏輯要更為復(fù)雜，使得時(shí)間復(fù)雜度的常系數(shù)會(huì)大一些，因此只有當(dāng)n和p具有一定規(guī)模的時(shí)候，DCQ算法才會(huì)快于Lucene。

（2）因?yàn)楝F(xiàn)代搜索引擎都帶有完善的跳表機(jī)制，所以只有當(dāng)文檔被t2j或者t3k命中時(shí)，在試圖收集該文檔的過(guò)程中才會(huì)觸發(fā)堆調(diào)整。也就是說(shuō)：只有在t2j或者t3k所命中的文檔號(hào)分布比較稠密的情況下，Lucene對(duì)所有命中文檔進(jìn)行收集打分的時(shí)間復(fù)雜度才會(huì)達(dá)到Θ(N(nlbn+plbp))。

因此，需要有一種高效的預(yù)測(cè)機(jī)制來(lái)決策DCQ算法的使用時(shí)機(jī)。

3.2 性能函數(shù)

為簡(jiǎn)化問(wèn)題，不妨令s1=+t11+t12…+t1m，并假設(shè)p=0，即沒(méi)有SHOULD子句（有SHOULD子句的情況可以在本節(jié)所提方法基礎(chǔ)上很容易地進(jìn)行擴(kuò)展）：

本文把某個(gè)特定算法針對(duì)查詢q的性能定義為：

QPSmethod表示在method算法下每秒處理完成q的次數(shù)（queries per second）。

定義算法m1對(duì)m0的相對(duì)性能為：

從3.1節(jié)的分析可以看出，DCQ算法的性能取決于兩個(gè)因素：

（1）MUST_NOT子句的總數(shù)n；

（2）s1和t2j所命中的文檔號(hào)分布情況。

因此可以把DCQ對(duì)Lucene的相對(duì)性能表達(dá)式寫(xiě)成：

其中，dist(t)表示t所命中的文檔號(hào)在自然數(shù)域上的分布情況。

為簡(jiǎn)化問(wèn)題，近似地以cost(t)來(lái)替代dist(t)，cost(t)是t所命中的文檔頻數(shù)估計(jì)值。于是有：

又因?yàn)槿藗兿Ｍ麖目傮w上來(lái)考慮所有SHOULD子句，所以近似地以式（9）來(lái)替代cost(s1),cost(t21),cost(t22),…,cost(t2n)。

從而，perfDCQ|Lucene(q)又可以進(jìn)一步簡(jiǎn)化為：

令a=cost(s1),b=avgcost(t21,t22,…,t2n)，則有：

顯然，當(dāng)f(n,a,b)＞0時(shí)，應(yīng)該使用DCQ算法來(lái)對(duì)文檔進(jìn)行收集打分。

3.3 性能的回歸預(yù)測(cè)

3.3.1 回歸模型的提出

如果可以擬合出f(n,a,b)，那么就可以比較準(zhǔn)確地決策DCQ算法的使用時(shí)機(jī)。

根據(jù)3.1節(jié)的分析可以看出，當(dāng)p=0時(shí)，Lucene的時(shí)間復(fù)雜度為Θ(Nnlbn)，而DCQ的時(shí)間復(fù)雜度為Θ(Nn)。也就是說(shuō)：

聯(lián)立式（6）、（11）、（12）1)f(x)∝g(x)表示f(x)與g(x)線性相關(guān)。，有：

因此，可以用一個(gè)關(guān)于lbn的線性函數(shù)去擬合f(n,a,b)：

為了驗(yàn)證上述想法，隨機(jī)構(gòu)建了一些滿足表達(dá)式（4）的查詢，并取一段連續(xù)自然數(shù){ni}進(jìn)行實(shí)驗(yàn)，得到對(duì)應(yīng)的{yi|yi=f(ni,a,b)}。

通過(guò)式（15）求出{lbni}與{yi}的相關(guān)系數(shù)：

發(fā)現(xiàn)min(cr)≥0.85，說(shuō)明在a、b給定的情況下，{lbni}與{yi}呈強(qiáng)線性相關(guān)。

3.3.2 參數(shù)α、β的求解

現(xiàn)在的問(wèn)題就是如何求解參數(shù)α和β。顯然，一定可以選取到一系列形式簡(jiǎn)單的函數(shù)u1(a,b),u2(a,b),…,uK(a,b)，使得：

β同理（以下的討論將以α的計(jì)算為例子，β的計(jì)算采用完全相同的方法，不再贅述）。

為便于計(jì)算，這里選取K=4，即有：

令u(a,b)=＜u1(a,b),u2(a,b),u3(a,b),u4(a,b)＞,k=＜k1,k2,k3,k4＞T，則有：

現(xiàn)在的目標(biāo)是求出向量k。由于向量k有4個(gè)參數(shù)，因此至少需要設(shè)置4組a、b的值，并通過(guò)實(shí)驗(yàn)得出它們各自對(duì)應(yīng)的α值。

本文隨機(jī)選定兩組詞項(xiàng)集來(lái)進(jìn)行實(shí)驗(yàn)：一組是高頻詞項(xiàng)集，其平均文檔頻數(shù)（document frequency）[16]為H；另一組是低頻詞項(xiàng)集，其平均文檔頻數(shù)為L(zhǎng)。

由于H和L的值都比較大，不妨取它們的對(duì)數(shù)，令h=lbH，l=lbL。這樣就可以利用h和l生成4個(gè)組合。

把式（20）代入式（19）可以得到：

進(jìn)而可以求得：

3.3.3 ui的選取

剩下的最后一個(gè)問(wèn)題就是ui的選取，ui必須滿足下述兩個(gè)條件：

（1）必須使得矩陣U可逆，這是向量k可計(jì)算的首要條件；

（2）ui需要能反映出一定的物理意義，以使得本文方法是可解釋的。

鑒于此，選取如表1所示的4個(gè)函數(shù)。

其中，u1、u2覆蓋了a、b的任意線性組合；u3考慮了a、b在二次冪空間上的影響；u4實(shí)際上是a、b調(diào)和平均值的一半，用以表示a、b的調(diào)和程度對(duì)結(jié)果的影響。

Table 1 Selection ofui表1 ui的選取

把ui代入式（20），得到：

可以計(jì)算出U的逆矩陣：

顯然，因?yàn)閔＞l，所以U-1是可計(jì)算的，即矩陣U可逆。進(jìn)而，把式（24）代入式（22）就可以求解出向量k。

有了向量k以后，在查詢處理的過(guò)程中，根據(jù)3.2節(jié)的定義，可以計(jì)算出a、b，并根據(jù)表1求得ui(a,b)的值，進(jìn)而代入式（20）、（21），求得α（β同理），得到式（14）所示的相對(duì)性能預(yù)測(cè)函數(shù)。

為了容許一些誤差，當(dāng)相對(duì)性能函數(shù)大于某個(gè)略大于0的閾值時(shí)，才選取DCQ算法。本文設(shè)置該閾值為5。也就是說(shuō)，只有當(dāng)DCQ算法的預(yù)測(cè)性能比Lucene至少提高5%時(shí)，才會(huì)選擇使用DCQ算法進(jìn)行文檔收集打分。

而針對(duì)查詢中同時(shí)包含MUST、MUST_NOT和SHOULD子句的情況，即式（2）的情況，會(huì)先把查詢拆分為如下形式進(jìn)行預(yù)測(cè)：

（1）如果DCQ算法處理q1和q2的效率都比較高，則采用DCQ算法；

（2）如果DCQ算法處理q1和q2的效率都比較低，則采用Lucene現(xiàn)行算法；

（3）如果DCQ算法處理q1的效率比較高，而處理q2的效率比較低，則對(duì)q1采用DCQ算法，而對(duì)q2采用Lucene現(xiàn)行算法；

（4）如果DCQ算法處理q1的效率比較低，而處理q2的效率比較高，則對(duì)q1采用Lucene現(xiàn)行算法，而對(duì)q2采用DCQ算法。

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

4.1 實(shí)驗(yàn)工具、數(shù)據(jù)和評(píng)價(jià)指標(biāo)

本文使用了著名開(kāi)源搜索引擎Lucene來(lái)進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)中，采用了包含33 332 621個(gè)詞條的維基百科數(shù)據(jù)集，并按照高頻、中頻、低頻的頻數(shù)分別隨機(jī)抽取100個(gè)詞項(xiàng)，如表2所示。

Table 2 Statistics for sampled terms set表2 所抽取詞項(xiàng)集的統(tǒng)計(jì)信息

利用上述詞項(xiàng)，構(gòu)建出如表3所示的若干種查詢。

Table 3 Constructing queries表3 構(gòu)建查詢

根據(jù)3.3.3節(jié)的描述，同時(shí)包含MUST、MUST_ NOT和SHOULD子句的查詢，最終將歸結(jié)到式（25）所示的兩種查詢，故而本文僅對(duì)f1-must-p-f2-should和f1-must-n-f2-mustnot這兩種情況進(jìn)行實(shí)驗(yàn)。

取n、p從3到9，并為每個(gè)n、p值給定查詢結(jié)構(gòu)，分別隨機(jī)生成50個(gè)查詢用于進(jìn)行評(píng)測(cè)，并采用QPS作為評(píng)價(jià)指標(biāo)：

其中|Q|=50。

4.2 DCQ算法的相對(duì)性能及其回歸預(yù)測(cè)

利用上述數(shù)據(jù)集分別對(duì)DCQ和Lucene進(jìn)行實(shí)驗(yàn)，求得各QPS值，并利用式（6）求得DCQ的相對(duì)性能perfDCQ|Lucene(q)，如圖1所示。

圖1的橫坐標(biāo)是lbn（或者lbp），藍(lán)色的是相對(duì)性能曲線，可以觀察到每條曲線近似地呈直線增長(zhǎng)。進(jìn)一步采用最小二乘法，對(duì)每條曲線做線性回歸，并求出其各自的相關(guān)系數(shù)，如表4所示。

Table 4 Performance fitting表4 性能曲線的擬合

把線性回歸所求得的關(guān)于lbn的線性函數(shù)繪制在圖1上。直觀上看，回歸曲線（紅色的）非常接近原來(lái)的性能曲線。另外，還通過(guò)式（15）計(jì)算出各組數(shù)據(jù)的相關(guān)系數(shù)，發(fā)現(xiàn)最小的相關(guān)系數(shù)為0.853，說(shuō)明lbn與f呈強(qiáng)線性相關(guān)。這就驗(yàn)證了3.3節(jié)提出的相對(duì)性能線性假設(shè)的合理性。

把表4的數(shù)據(jù)代入式（22）、（24），求解得到各組k向量，并在查詢處理運(yùn)行時(shí)刻套用式（19）、（21）求得在特定查詢下的α、β值，進(jìn)而得到式（14）所示的相對(duì)性能回歸函數(shù)，即可預(yù)測(cè)出在該查詢下，DCQ算法是否更優(yōu)。

Fig.1 Relative performance curve and linear fitting圖1 相對(duì)性能曲線與線性擬合

4.3 結(jié)合性能回歸預(yù)測(cè)器的總體性能

當(dāng)相對(duì)性能的預(yù)測(cè)值超過(guò)5%時(shí)，采用DCQ算法進(jìn)行文檔收集打分。本文使用了十折交叉驗(yàn)證法（10-fold cross validation），求得最終的性能結(jié)果，如圖2和圖3所示。

Fig.2 Relative performance whenq=+s1-t21-t22…-t2n圖2 處理q=+s1-t21-t22…-t2n時(shí)的相對(duì)性能

Fig.3 Relative performance whenq=+s1t31t32…t3p圖3 處理q=+s1t31t32…t3p時(shí)的相對(duì)性能

可以觀察到，在各種查詢下，性能預(yù)測(cè)器都能很好地進(jìn)行預(yù)測(cè)，并選用適當(dāng)?shù)奈臋n收集打分算法。n（或者p）越大，性能的提升越顯著。注意到在某些查詢下，帶預(yù)測(cè)器的復(fù)合算法性能有所下降（相對(duì)性能小于0），但下降幅度不大（-6%以內(nèi)）。原因是：實(shí)驗(yàn)中每次迭代都是先運(yùn)行復(fù)合算法，再運(yùn)行Lucene，這就使得在運(yùn)行Lucene時(shí)，緩存（cache）中還留有一定的數(shù)據(jù)，進(jìn)而讓Lucene看似有略高一點(diǎn)的性能?？傮w來(lái)說(shuō)，帶預(yù)測(cè)器的復(fù)合算法在各種查詢情況下都不差于Lucene。

5 總結(jié)

在信息檢索的傳統(tǒng)領(lǐng)域，本文提出了一種針對(duì)復(fù)雜布爾查詢的優(yōu)化方法——DCQ算法，通過(guò)利用這種查詢的一些重要特性，避免了在文檔收集打分過(guò)程中的堆調(diào)整，進(jìn)而優(yōu)化了查詢性能（特別是當(dāng)SHOULD子句或者M(jìn)UST_NOT子句較多時(shí)）。為了進(jìn)一步完善本文方法，提出了一種對(duì)相對(duì)性能的回歸預(yù)測(cè)機(jī)制，能比較準(zhǔn)確地預(yù)測(cè)DCQ算法的使用時(shí)機(jī)。通過(guò)評(píng)測(cè)發(fā)現(xiàn)，帶性能預(yù)測(cè)器的復(fù)合算法能夠大大地提高Lucene的查詢性能。

[1]Manning C D,Raghavan P,Schütze H.Introduction to information retrieval[M].Cambridge:Cambridge University Press,2008:12-13.

[2]Salton G,Fox E A,Wu H.Extended Boolean information retrieval[J].Communications of the ACM,1983,26(11): 1022-1036.

[3]Sanderson M,Croft W B.The history of information retrieval research[J].Proceedings of the IEEE,2012,100(Special Centennial Issue):1444-1451.

[4]Chen Qiang,Ye Bing,Zhu Yu’e.Internet tutorial[M].2nd ed.Beijing:Tsinghua University Press,2005:209-212.

[5]Djurup R.Your guide to Google Web search[M].[S.l.]:Rebidu, 2010:143-144.

[6]Voorhees E M.Query expansion using lexical-semantic relations[C]//Proceedings of the 17th Annual International SIGIR Conference on Research and Development in Information Retrieval,Dublin,1994.London:Springer,1994:61-69.

[7]Xu Jinxi,Croft W B.Query expansion using local and global document analysis[C]//Proceedings of the 19th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,Zurich,1996.New York: ACM,1996:4-11.

[8]Kim Y,Seo J,Croft W.B.Automatic boolean query suggestion for professional search[C]//Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval,Beijing,2011.New York: ACM,2011:825-834.

[9]Griffith C.WESTLAW’s WIN:not only natural,but new[J]. Information Today,1992,9(9):9-11.

[10]Wang Shihui,Jia Guanxin.Patent information retrieval by using SooPAT[J].Information Research,2012(1):94-96.

[11]Jiang Meng,Cui Peng,Liu Rui,et al.Social contextual recommendation[C]//Proceedings of the 21st ACM International Conference on Information and Knowledge Management, Maui,2012.New York:ACM,2012:45-54.

[12]Reips U D,Garaizar P.Mining twitter:a source for psychological wisdom of the crowds[J].Behavior Research Methods,2011,43(3):635-642.

[13]Ronen I,Guy I,Kravi E,et al.Recommending social media content to community owners[C]//Proceedings of the 37th International ACM SIGIR Conference on Research and Development in Information Retrieval,Gold Coast,2014. New York:ACM,2014:243-252.

[14]Croft W B,Metzler D,Strohman T.Search engines:information retrieval in practice[M].Reading,USA:Addison-Wesley,2010:168-171.

[15]Pugh W.Skip lists:a probabilistic alternative to balanced trees[J].Communications of theACM,1990,33(6):668-676.

[16]Leskovec J,Rajaraman A,Ullman J D.Mining of massive datasets[M].Cambridge:Cambridge University Press,2014: 1-17.

附中文參考文獻(xiàn)：

[4]陳強(qiáng),葉兵,朱玉娥.Internet應(yīng)用教程[M].2版.北京:清華大學(xué)出版社,2005:209-212.

[10]王世慧,賈冠昕.利用SooPAT檢索專利信息[J].情報(bào)探索,2012(1):94-96.

HUANG Da was born in 1991.He is an M.S.candidate at School of Electronics Engineering and Computer Science,Peking University.His research interests include information retrieval and Web data mining.

黃達(dá)（1991—），男，廣東梅州人，北京大學(xué)信息科學(xué)技術(shù)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)樾畔z索，網(wǎng)絡(luò)數(shù)據(jù)挖掘。

YAN Hongfei was born in 1973.He received the Ph.D.degree in computer science from Peking University in 2002.Now he is an associate professor at Peking University.His research interests include information retrieval and distributed computing.

閆宏飛（1973—），男，黑龍江哈爾濱人，2002年于北京大學(xué)獲得博士學(xué)位，現(xiàn)為北京大學(xué)副教授，主要研究領(lǐng)域?yàn)樾畔z索，分布式計(jì)算。發(fā)表學(xué)術(shù)論文50多篇，作為負(fù)責(zé)人承擔(dān)的國(guó)家級(jí)項(xiàng)目包括自然科學(xué)基金、核高基項(xiàng)目、863計(jì)劃等。

Optimization for Collecting and Scoring Documents for Complex Boolean Query*

HUANG Da+,YAN Hongfei2
School of Electronics Engineering and Computer Science,Peking University,Beijing 100871,China
+Corresponding author:E-mail:huangda@net.pku.edu.cn

Although Boolean query has been proposed very early in information retrieval,most research on Boolean query focuses on homogeneous Boolean operation.Few researchers paid attention to complex Boolean query,while such query is used more and more frequently,e.g.in text-based recommendation.In order to make complex Boolean query execute more efficiently,this paper proposes a new strategy,DCQ(DAAT for complex query)algorithm, which is based on DAAT(document-at-a-time)framework.By comparing DCQ algorithm with the well-known open-source search engine,Lucene,it shows a promising improvement on performance.Besides,this paper proposes a method for performance regression,which can decide when to use DCQ algorithm accurately.Experiments show that the compound algorithm with performance regression is much better than the algorithm for collecting and scoring documents used in Lucene.

complex Boolean query;optimizing query;performance regression

A

：TP391

10.3778/j.issn.1673-9418.1511044

*The National Basic Research Program of China under Grant No.2014CB340400(國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973計(jì)劃));the National Natural Science Foundation of China under Grant Nos.61272340,61272340(國(guó)家自然科學(xué)基金).

Received 2015-10,Accepted 2015-12.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-12-16,http://www.cnki.net/kcms/detail/11.5602.TP.20151216.1021.002.html