基于動(dòng)態(tài)文檔集的索引技術(shù)

(1.中國科學(xué)院 軟件研究所， 北京 100190； 2.中國科學(xué)院 研究生院， 北京 100049)



摘 要：倒排文件是全文檢索中廣泛使用的索引結(jié)構(gòu)，對靜態(tài)文檔集合建立倒排索引的研究已有較長時(shí)間。隨著計(jì)算機(jī)技術(shù)的發(fā)展，需要存儲的數(shù)據(jù)越來越大。同時(shí)特定的應(yīng)用領(lǐng)域如新聞搜索、桌面搜索等對實(shí)時(shí)更新性能要求較高，這需要使用有效的索引更新策略，也稱動(dòng)態(tài)索引。描述了常用的動(dòng)態(tài)索引技術(shù)，并詳細(xì)分析了其使用代價(jià)。

關(guān)鍵詞：倒排表； 索引的建立； 索引更新

中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：A

文章編號：10013695(2009)01001504



Index technique for dynamic corpus

PAN Longxi1，2， SUN Le1



(1.Institute of Software， Chinese Academy of Sciences， Beijing 100190， China; 2.Graduate School， Chinese Academy of Sciences， Beijing 100049， China)

Abstract:Inverted list is the main data structure used in IR. The offline index construction about static corpus has been under research for a long time. As the development of computer， thedatacapacity become larger and larger and in some specific domains such as news search and desktop search which demand high quality about index update， all of these needs us to find a efficient index update way. This paper described and analyzed several efficient index update strategy in common use.

Key words：inverted list; index construction; index update



0 引言

全文檢索技術(shù)在人們的生活中發(fā)揮了重要的作用，小到文件查找，大到圖書館檢索、搜索引擎等領(lǐng)域。傳統(tǒng)的全文檢索技術(shù)更多的是著重于靜態(tài)文檔集合索引的建立，但是隨著數(shù)據(jù)量的增加和變化，單純的靜態(tài)索引已經(jīng)不能滿足應(yīng)用要求，索引更新是必需的。這就需要找到一種有效的動(dòng)態(tài)更新倒排索引策略。本文綜述了面向動(dòng)態(tài)應(yīng)用環(huán)境如新聞搜索、桌面搜索領(lǐng)域。對索引實(shí)時(shí)更新要求比較嚴(yán)格的應(yīng)用技術(shù)，通常稱之為動(dòng)態(tài)索引技術(shù)或在線索引技術(shù)。

1 倒排索引簡介

一個(gè)文件就是一系列有位置順序的詞的集合，通常稱之為正排表或詞向量。在一個(gè)文件中查找一個(gè)指定的詞是字符串匹配的過程，這種查找效率不符合人們搜索信息的習(xí)慣。全文檢索中使用倒排表索引結(jié)構(gòu)，對于出現(xiàn)在文件中的每個(gè)詞語，倒排表包含了一個(gè)出現(xiàn)該詞的文檔列表。對于一個(gè)詞語t，它的倒排表形式如下:

(ft;〈di， fdi，t，〈ldi，1，ldi，2，…，ldi， fdi，t〉〉*)

其中：ft為該詞出現(xiàn)的頻率；di為文檔的編號； fdi，t表示詞t在文檔di中出現(xiàn)的頻率；ldi，i表示詞t在文檔di中第i次出現(xiàn)的位置。倒排表被證明是組織大規(guī)模信息檢索系統(tǒng)最有效的數(shù)據(jù)結(jié)構(gòu)[1，2]。

對一個(gè)待處理的文檔集建立倒排索引步驟如下：

a)掃描待處理文檔集。

b)對文檔進(jìn)行預(yù)處理，包括分詞、去停用詞等。

c)對于文檔中的每個(gè)索引詞，在內(nèi)存中建立倒排索引。

d)內(nèi)存中倒排索引轉(zhuǎn)移到外存中存儲。

2 靜態(tài)索引

靜態(tài)索引是相對動(dòng)態(tài)索引而言的，也就是指對文檔集建立倒排索引后不再發(fā)生索引更新。下面從兩點(diǎn)來簡單描述索引的建立：倒排索引的建立算法；倒排索引建立過程中內(nèi)存的控制和使用。這兩點(diǎn)也是建立倒排索引比較重要的地方。

2.1 倒排索引的建立

建立倒排索引是全文檢索應(yīng)用的核心和基礎(chǔ)。在進(jìn)行關(guān)鍵詞的查詢之前必須先建立好倒排索引，這也是全文檢索快速返回結(jié)果的原因所在。下面介紹幾種常用的建立倒排索引的策略[3]:

a）基于內(nèi)存的策略

基于內(nèi)存的建立倒排索引過程把倒排索引看做一個(gè)二維矩陣，索引詞表示矩陣中的行，文檔列表則為矩陣中的列，相對應(yīng)的元素表示某詞在某文檔中出現(xiàn)的頻率。掃描文檔過程就是填充矩陣的過程。對于超出計(jì)算機(jī)內(nèi)存大小的倒排索引的建立則必須借助操作系統(tǒng)的虛擬內(nèi)存技術(shù)。

b）基于外存的合并策略

一般情況下，待建立的倒排索引的大小遠(yuǎn)遠(yuǎn)大于內(nèi)存的容量。這種情況下可以把文檔集劃分成一個(gè)個(gè)小的部分，使得每一部分索引能在內(nèi)存中容納下，每一部分產(chǎn)生一個(gè)子索引，然后對這些子索引實(shí)行多路歸并以產(chǎn)生最終的倒排索引。

c）基于外排序的策略

掃描文檔過程其實(shí)就是查找每個(gè)詞在每篇文檔中的出現(xiàn)情況。給詞和文檔編號以后，可以把建立倒排索引的過程看成是統(tǒng)計(jì)三元組〈t， d， f 〉序列。其中：t、d分別為詞編號、文檔編號； f為詞t在文檔d中的頻率。把在內(nèi)存中三元組序列按詞排序后產(chǎn)生的結(jié)果寫入外存的臨時(shí)文件中，待文檔集全部掃描完畢后再運(yùn)用外排序的方法對外存中的文件進(jìn)行歸并。這種方法需要在內(nèi)存中保持詞到詞編號映射的數(shù)據(jù)結(jié)構(gòu)。

2.2 內(nèi)存的使用和控制

倒排索引的建立過程就是對于文檔中每個(gè)位置所出現(xiàn)的詞，先在內(nèi)存中的詞典查找相關(guān)的詞，找到其指向的倒排表，再添加記錄到倒排表中。所以在內(nèi)存中需要解決兩個(gè)問題：索引詞典的存儲；倒排表的存儲。

索引詞典的存儲可以采用二元搜索樹、Splay樹、哈希表、鍵樹、B樹等。哈希表和鍵樹的查找是線性時(shí)間，與索引詞典的大小無關(guān)。但鍵樹由于指針開銷，浪費(fèi)空間嚴(yán)重，實(shí)際很少使用。B樹搜索樹的查找時(shí)間是log（詞典長度）的。在這些數(shù)據(jù)結(jié)構(gòu)當(dāng)中，哈希表提供了更好的性能[4]。

對于索引詞倒排表的存儲，如果使用定長數(shù)組的存儲，必須兩次掃描文檔集以先確定索引詞的相關(guān)參數(shù)再分配定長空間，不符合性能要求。單趟掃描的方法一般采用動(dòng)態(tài)數(shù)組和鏈表等可以動(dòng)態(tài)增長空間的數(shù)據(jù)結(jié)構(gòu)。為了節(jié)約存儲空間，在實(shí)際使用中通常采用基于游程編碼的壓縮方式存儲倒排表[5]。

3 增量索引

前面描述了全文檢索中靜態(tài)索引相關(guān)技術(shù)，在實(shí)際應(yīng)用中不但要建立倒排索引，同時(shí)還需要添加文檔并及時(shí)地更新索引，使得新增加的文檔能夠及時(shí)地反映到檢索結(jié)果中，這就是下面要討論的增量技術(shù)，通常也稱之為在線索引技術(shù)。無論采用何種更新策略，更新的過程通常是先在內(nèi)存中建立每個(gè)索引詞的倒排表。當(dāng)內(nèi)存的容量達(dá)到一定值時(shí)就必須把內(nèi)存中的倒排表寫回外存中存儲，然后清空內(nèi)存，如此循環(huán)。根據(jù)內(nèi)存中索引寫回外存的策略不同，增量索引的方法大致有三種[6，7]，下面分別詳細(xì)描述。為了用公式量化增量索引的代價(jià)，假定索引建立和更新整個(gè)過程的代價(jià)為數(shù)據(jù)建立和移動(dòng)的次數(shù)，包括在內(nèi)存中建立倒排表的代價(jià)和轉(zhuǎn)移到外存的代價(jià)，忽略磁盤尋道時(shí)間。假設(shè)整個(gè)文檔集中索引詞出現(xiàn)的次數(shù)為N（包括重復(fù)出現(xiàn)的），內(nèi)存中存儲的索引詞詞典大小為v，內(nèi)存中能夠容納m個(gè)posting，其中一個(gè)posting定義為一個(gè)索引詞的倒排表中的一項(xiàng)記錄，也就是一個(gè)索引詞在一篇文檔的一次出現(xiàn)，那么創(chuàng)建完索引需要[N/m]次交換過程，每次交換為一次索引更新過程。

3.1 重建

重建方法是最簡單最直接的更新索引策略，顧名思義就是從頭重新建立索引，也就是每次有更新發(fā)生時(shí)就對整個(gè)文檔集重新建立索引，丟棄原來已有的索引。重新建立索引所需要的代價(jià)為

cost(N，m，v)=∑N/mi=1∑N/mj=1(m+m log v)≈(m+m log v)×O(N2)

其中:m為一個(gè)內(nèi)存子索引一次轉(zhuǎn)移的代價(jià)，以一個(gè)posting的讀寫為單位；m log v為一次子索引在內(nèi)存中建立的代價(jià)。

3.2 原地(inplace)

原地方法就是對于新增加的文檔，盡量不改變外存中原來已經(jīng)建立的索引。對于新建立的倒排索引，按照每個(gè)索引詞查找已經(jīng)存在的倒排表，查看其剩余空間，如果空間足夠容納當(dāng)前倒排表大小就插入當(dāng)前的倒排表；否則新分配一個(gè)更大的空間合并原來和新的倒排表，舍棄原來的倒排表。圖1在這種方式下，因?yàn)閷τ诿總€(gè)索引詞都需要去尋找其對應(yīng)的倒排表，所以其隨機(jī)尋道次數(shù)較多，在計(jì)算其代價(jià)時(shí)并不考慮隨機(jī)尋道時(shí)間。根據(jù)外存中索引是否連續(xù)又可以細(xì)分為兩種。倒排表的連續(xù)是指一個(gè)索引詞的倒排表的數(shù)據(jù)是在連續(xù)的空間中存放的，而不是通過其他指針鏈接的方式組合起來的。因?yàn)橥獯嬷械乃饕贿B續(xù)會(huì)影響查詢性能，本文僅討論它的連續(xù)方式的代價(jià)。

圖1(a)(b)的左邊為九個(gè)索引詞已存在的倒排表，灰色表示已占用的空間，白色為剩余空間；圖1(a)(b)的右邊為待添加的子索引，其中第五個(gè)詞的剩余空間不足，重新分配空間并拷貝數(shù)據(jù)，丟棄原來空間。

這種方法的關(guān)鍵點(diǎn)是預(yù)分配空間策略，也就是每次分配新空間時(shí)分配r＞1倍所需空間，以備將來使用。每當(dāng)有內(nèi)存中的子索引需要轉(zhuǎn)移到外存中時(shí)，如果剩余的分配空間足夠容納當(dāng)前的倒排表則寫到原剩余空間上；否則重新分配空間并轉(zhuǎn)移數(shù)據(jù)。

在該方式下一個(gè)索引詞的倒排表平均移動(dòng)次數(shù)是r/（r-1)次[8]。例如，如果r=1.25，那么倒排表的平均移動(dòng)次數(shù)為5次。原地方法的代價(jià)為

cost(N，m，v)=∑N/mi=1m log v+∑N/mi=1rm/(r-1)≈(log v+r/(r-1))×O(N)

3.3 合并(rebuild)

合并方法就是對于新增加的子索引獨(dú)立寫入到外存中，然后與已經(jīng)存在的索引實(shí)現(xiàn)合并。合并后產(chǎn)生新的索引并拋棄原來的子索引。它與基于原地的策略不同之處是直接分配新空間存儲合并后的子索引并丟棄原來的空間。流行的開源全文索引引擎Lucene就是采用了這種策略。一個(gè)子索引在Lucene中稱為一個(gè)segment。Lucene就是先產(chǎn)生多個(gè)segments，然后實(shí)現(xiàn)合并。Remerge方法又根據(jù)硬盤上是否能存在多個(gè)子索引以及合并的順序分為幾種不同的合并方案。最簡單的方案就是不合并。這種方案的外存中存在多個(gè)不連續(xù)的子索引，大大降低了查詢的性能。一般查詢的時(shí)間與硬盤上存在的子索引個(gè)數(shù)成反比，這是因?yàn)樗阉鲿r(shí)需要讀取多個(gè)子索引并合并查詢結(jié)果。這種方式難以滿足應(yīng)用需求。下面分析幾種常用的合并方案。為了描述索引合并的整個(gè)過程，可以把索引合并的過程看成是數(shù)據(jù)結(jié)構(gòu)中一棵樹的構(gòu)建過程，樹中兒子節(jié)點(diǎn)即為參與合并的子索引，父子節(jié)點(diǎn)為合并后的索引。

3.3.1 立即合并

立即合并就是在任何時(shí)候，只要一有子索引寫入到外存中，就與原來外存中已經(jīng)存在了的索引合并。所以它在硬盤中最終生成的索引是連續(xù)的。索引連續(xù)是指一個(gè)索引詞的倒排表在外存中是占用連續(xù)的存儲空間。

圖2中灰色圓圈表示硬盤上存在的索引，白色圓圈表示從內(nèi)存剛轉(zhuǎn)入到外存的子索引。一個(gè)父節(jié)點(diǎn)就是其兒子節(jié)點(diǎn)合并的結(jié)果。這種方案的代價(jià)為

cost(N，m，v)=∑N/mi=1m log v+∑N/mi=1∑N/mj=im≈log v×N+m×O(N2)

3.3.2 Logarithmic合并

這種合并方案為外存中存在的子索引添加一個(gè)整型標(biāo)記，即輩分，以記錄其參與合并的次數(shù)。一個(gè)剛要寫入外存中的內(nèi)存索引輩分標(biāo)記為1，每合并一次，合并后的索引輩分就加1。當(dāng)硬盤上存在兩個(gè)輩分相同的索引就進(jìn)行合并，輩分加1，這樣又會(huì)觸發(fā)新的合并，直到不再發(fā)生合并時(shí)為止。如圖3所示，這種方法也允許外存中存在多個(gè)子索引，最后每個(gè)子索引的輩分不一樣。

圖3中灰色圓圈表示外存中曾存在的索引，白色圓圈表示觸發(fā)合并的內(nèi)存子索引。剛轉(zhuǎn)移到外存的內(nèi)存子索引的輩分編號為1。參與了一次合并后產(chǎn)生的索引輩分?jǐn)?shù)加1。

這種方法的代價(jià)為

cost(N，m，v)=∑N/mi=1m log v+∑N/mi=1m log N/m≈log v×N+O(N×log N/m)

3.3.3 幾何歸并

這種合并策略關(guān)鍵點(diǎn)是在合并的時(shí)候考慮了子索引的大小[8]。定義一個(gè)索引詞的倒排表大小為其包含的posting（見第3章中的定義）數(shù)目，定義一個(gè)子索引大小為其包含所有索引詞的倒排表大小的總和。幾何歸并定義了控制參數(shù)r來限制子索引的大小，并把外存中索引劃分為幾個(gè)不同的區(qū)間:1，2，3，…，k，子索引根據(jù)大小歸屬于對應(yīng)的區(qū)間。假如內(nèi)存中緩存的索引大小為m，則外存中第k區(qū)間的子索引的大小控制在[rk-1m，(r-1)rk-1m]內(nèi)。每一區(qū)間最終只允許存在一個(gè)獨(dú)立的子索引，同時(shí)存在一個(gè)以上就觸發(fā)了合并。這樣就可以有效控制每一個(gè)區(qū)間的子索引大小，同時(shí)可以控制參與合并的子索引大小和合并以后的子索引大小。當(dāng)合并后的子索引大小超過限定值時(shí)就必須根據(jù)合并后的大小劃分到對應(yīng)的區(qū)間中。如圖4所示，這種方法考慮了子索引合并時(shí)子索引大小的概念，并基于這樣一個(gè)假設(shè)：具有最少合并代價(jià)的過程是盡量合并同等大小的子索引。

圖4中，r=3，m=1時(shí)partion 1的大小在[1，2]，partion 2的大小在[3，6]，partion 3的大小在[9，18]。一個(gè)父節(jié)點(diǎn)就是一次合并過程。

因?yàn)樗饕罱K大小和內(nèi)存中緩存的索引大小是固定的，如前述子索引合并的過程是一棵帶權(quán)樹的構(gòu)建，合并具有相同大小的子索引產(chǎn)生的樹的深度較小，則合并相近大小的子索引能夠產(chǎn)生最少帶權(quán)路徑。例如幾何歸并只合并在同一區(qū)間的子索引，就是盡量合并大小差別不大的子索引。

當(dāng)定義了外存中每一區(qū)間的子索引大小后，事實(shí)上也就定義了索引的合并順序和大小。對于給定大小的N、m、v和r，第k區(qū)間的子索引大小取值在[0，rk-1m，2rk-1m，3rk-1m，…，(r-1)rk-1m]離散值區(qū)間循環(huán)，共有(N/m)/rk個(gè)循環(huán)。樹的深度h=「log (N/m)，則幾何歸并的代價(jià)為

cost(N，m，v)=N log v+∑i=hi=1(N/m)/ri∑rj=1(j-1)mri-1=

N log v+∑hi=1N/ri×(r-1)ri/2=log v×N+(r-1)N/2×logr(N/m)

3.4 Hybridway（結(jié)合inplace和remerge）

有學(xué)者研究表明，文檔集中索引詞的分布符合語言學(xué)中的齊普夫(Zipf)定律：有一部分出現(xiàn)頻率較高的常用索引詞的倒排表長度（包含posting的數(shù)目）較長?；诤喜⒌脑隽坎呗?，每次都必須讀取整個(gè)倒排表，合并后寫入到新的存儲空間中去，比較適合短的倒排表；而inplace無須移動(dòng)已有的倒排表，比較適合處理長的倒排表。可以結(jié)合inplace和remerge方法的優(yōu)點(diǎn)來使用。通常預(yù)先設(shè)定一個(gè)T值，當(dāng)一個(gè)索引詞的倒排表大小小于T時(shí)就采用remerge策略；當(dāng)其倒排表大小超過T時(shí)就采用inplace合并策略[9]?；趇nplace和remerge的方法可以組合使用，例如inplace方案可以與以上提到的每一種remerge方法組合，同時(shí)又根據(jù)是否允許索引連續(xù)進(jìn)一步組合。由于其方案較多，本文不作詳細(xì)描述，有興趣的讀者可以參考文獻(xiàn)[10]。

在以上提到的增量索引策略中，rebuild方法是最簡單原始的方法，代價(jià)太大，僅僅適合于很小文檔集或者更新很少的場合。Inplace從公式來看是更新代價(jià)最低的，但是這僅僅考慮了數(shù)據(jù)的移動(dòng)，并沒有考慮磁盤的尋道時(shí)間，事實(shí)上正是由于inplace隨機(jī)尋道次數(shù)較多，inplace在大多數(shù)應(yīng)用場合性能遜色于remerge方法[6]；同時(shí)inplace還有一個(gè)缺點(diǎn)，其預(yù)分配空間策略會(huì)浪費(fèi)一定的空間。Remerge由于其合并策略的靈活性而使用較多。

4 文檔的刪除

在動(dòng)態(tài)環(huán)境下不但要添加文檔，還要?jiǎng)h除文檔。通常把清除倒排索引中已經(jīng)刪除了的文檔過程稱之為垃圾回收。對于重建增量索引策略，文檔的刪除是簡單的，就是不重建那些被刪除了的文檔。當(dāng)采用基于合并的更新策略，一種直接的做法是，每當(dāng)有文檔被刪除時(shí)就讀取對應(yīng)的倒排表并作更新。但是由于去除倒排表中已刪除文檔的編號需要解壓對應(yīng)索引詞的整個(gè)倒排表，這樣代價(jià)太大，難以滿足應(yīng)用需求常常采用一種偽刪除策略，用一個(gè)比特位向量來標(biāo)志已經(jīng)刪除了的文檔，在查詢時(shí)過濾掉已經(jīng)刪除了的文檔[11]。但這樣當(dāng)刪除文檔過多時(shí)會(huì)降低查詢的性能，所以當(dāng)刪除文檔占總文檔超出一定比例時(shí)必須進(jìn)行倒排表的更新。為了進(jìn)一步提高效率，往往把垃圾回收與索引更新的過程結(jié)合起來。假設(shè)已刪除文檔占總文檔的比例為r，當(dāng)子索引合并發(fā)生時(shí)，如果r＜p(預(yù)先設(shè)定值），合并子索引和對應(yīng)的標(biāo)志刪除的位向量（注意這個(gè)過程并不需要解壓倒排表，而只需讀寫倒排表和合并數(shù)據(jù)）；而當(dāng)r＞p時(shí)，才讀取并解壓子索引的倒排表，去除已刪除的文檔號后再壓縮合并成新的數(shù)據(jù)，這也是刪除過程的主要開銷所在。在原地更新索引策略中，刪除文檔的索引更新也可以采用上述的偽刪除策略來提高效率。

5 結(jié)束語

本文詳細(xì)敘述了全文索引中靜態(tài)索引的建立和索引動(dòng)態(tài)更新以及刪除的常用算法，詳細(xì)分析了幾種增量索引方案的使用代價(jià)，并把基于合并的更新描述成帶權(quán)樹的構(gòu)建，定量地說明為什么要盡量合并相同大小的子索引。通常來說，并沒有一種方案優(yōu)于另外一種方案，而是必須根據(jù)實(shí)際使用需求來選擇相應(yīng)的方案。比如查詢時(shí)間和建立索引的時(shí)間通常是一對折中[12]，允許不連續(xù)的索引存在則建立索引時(shí)間減少，但查詢時(shí)間增加；反之，如果索引必須連續(xù)則建立索引的時(shí)間增加，而查詢時(shí)間減少。所以在應(yīng)用時(shí)要根據(jù)自己的需求在不影響查詢效率的情況下采用相對應(yīng)的策略。

參考文獻(xiàn)：

［1］ZOBEL J， MOFFAT A， RAMAMOHANARAO K. Inverted files vs signature files for text indexing[J].ACM Trans on Database Systems，1998，23(4):453490. 

［2］ZOBEL J， MOFFAT A. Inverted files for text search engines[J]. ACM Computing Surveys， 2006，38(2):156.

［3］HEINZ S， ZOBEL J. Efficient singlepass index construction for text database[J]. Journal of the American Society for Information Science and Technology，2003，54(8):729731.

［4］ZOBEL J， HEINZ S， WILLIAMS H E. Inmemory hash tables for accumulating text vocabularies[J].Information Processing Letters，2001，80(6):271277.

［5］WITTEN I， MOFFAT A， BELL T. Managing gigabytes[M]. 2nd ed. San Francisco，California:Morgan Kaufmann Publishing， 1999.

［6］LESTER N，ZOBEL J， WILLIAMS H E. Inplace versus rebuild versus remerge:index maintenance strategies for text retrieval systems[C]//Proc of Australasian Computer Science Conference. 2004:1522.

［7］LESTER N， ZOBEL J， WILLIAMS H E.Efficient online index maintenance for contiguous inverted lists[J].Systems Information Processing and Management，2006，42(4):916933.

［8］LESTER N， MOFFAT A， ZOBEL J. Fast online index construction by geometric partitioning[C]//Proc ofACM CIKM Conference on Information and Knowledge Management. 2005:776783.

［9］TOMASIC A， GARCIAMOLINA H， KURT S. Incremental updates of inverted lists for text document retrieval[C]//Proc of ACM SIGMOD Conference on Management of Data. New York:[s.n.]，1994:289300.

［10］BUTTCHER S， CLARKE C L A， LUSHMAN B. Hybrid index maintenance for growing text collections[C]//Proc of the 29th ACM Conference on Research and Development on Information Retrieval. Seattle:[s.n.]， 2006.

［11］GUO Rejie， CHENG Xueqi， XU Hongbo，et al. Efficient online index maintenance for dynamic text collections by using dynamic balancing tree[C]//Proc of ACM Conference on Information and Knowledge Management. 2007.

［12］BUTTCHER S， CLARKE C L A. Indexing time vs query time tradeoff in dynamic information retrieval systems[C]//Proc of the 14th ACM Conference on Information and Knowledge Management. Bremen:[s.n.]， 2005.