基于版塊的論壇增量搜集策略

杜言琦，馬 軍

(山東大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 濟(jì)南 250101)

1 引言

隨著網(wǎng)絡(luò)的不斷發(fā)展，論壇作為Web信息交流共享平臺擁有數(shù)以百萬的用戶，論壇數(shù)據(jù)通常包含大量高價(jià)值的知識和信息，已經(jīng)成為許多Web應(yīng)用的重要數(shù)據(jù)源[1]。例如一些商業(yè)搜索引擎已經(jīng)開始利用論壇數(shù)據(jù)來改善它們的搜集質(zhì)量[2]。無論何種Web應(yīng)用，基礎(chǔ)的步驟是不斷從論壇站點(diǎn)中抓取新增數(shù)據(jù)，來維持對數(shù)據(jù)索引的增量更新，以保證檢索的實(shí)時(shí)性。

傳統(tǒng)的增量搜集技術(shù)是針對普通的靜態(tài)頁面[3]，調(diào)度的基本單位是單個(gè)頁面[4-5]，對論壇頁面進(jìn)行增量搜集的效率很低，因?yàn)檎搲军c(diǎn)有一些不同于普通站點(diǎn)的特征：屬于同一版塊的帖子和屬于同一帖子的回復(fù)通常都分布在多個(gè)頁面上；論壇更新速度快，帖子內(nèi)容增量式更新。傳統(tǒng)的增量搜集技術(shù)不適合進(jìn)行論壇數(shù)據(jù)的增量搜集。因此，尋找新穎的論壇增量搜集算法具有重要的學(xué)術(shù)和應(yīng)用價(jià)值。

通過觀察多個(gè)論壇，我們發(fā)現(xiàn)帖子一般是按照發(fā)布或最新回復(fù)時(shí)間排列在帖子列表頁上。通過對論壇版塊變化規(guī)律的統(tǒng)計(jì)，發(fā)現(xiàn)不同的版塊更新速度不同并且版塊的更新具有時(shí)間局部特性，據(jù)此我們提出了一種版塊權(quán)重的計(jì)算公式，給予不同版塊不同的權(quán)重，以此來確定對版塊的抓取頻率；提出一種確定抓取時(shí)間點(diǎn)的算法，根據(jù)版塊的局部時(shí)間規(guī)律來確定對版塊的抓取時(shí)間點(diǎn)。

本文的主要貢獻(xiàn)有：(1)以版塊為單位進(jìn)行增量調(diào)度而不是像現(xiàn)有大多數(shù)爬蟲以單個(gè)頁面為調(diào)度單位。(2)提出了基于版塊的增量抓取算法，獲得很高的準(zhǔn)確率和召回率。(3)提出了基于版塊的抓取調(diào)度算法，大幅減小系統(tǒng)總延遲。

2 相關(guān)工作

傳統(tǒng)增量搜集技術(shù)的核心理論依據(jù)是網(wǎng)頁的變化規(guī)律和以此為基礎(chǔ)的最優(yōu)化調(diào)度策略。對網(wǎng)頁變化規(guī)律的研究目前主要有兩種方法：一種是基于試驗(yàn)手段對Web中網(wǎng)頁采樣，通過搜集和檢查樣本的變化規(guī)律，從而估計(jì)整個(gè)Web的變化規(guī)律[3]。另一種是從理論上直接給網(wǎng)頁的變化建立數(shù)學(xué)模型，然后進(jìn)行分析和論證，最后試驗(yàn)驗(yàn)證該模型并估計(jì)相關(guān)參數(shù)，以此模型預(yù)測頁面的下次變化時(shí)間[4，12]。在當(dāng)前的研究中，網(wǎng)頁的變化一般被認(rèn)為是泊松過程[3]，即網(wǎng)頁兩次變化直接的時(shí)間間隔服從指數(shù)分布，以此來建立基本模型?；诰W(wǎng)頁變化模型，就要通過搜集來估計(jì)其參數(shù)[4-5]，以獲得網(wǎng)頁的變化頻率并推算下次變化時(shí)間。由于通常沒有足夠的時(shí)間和資源去獲得互聯(lián)網(wǎng)上每個(gè)頁面的變化時(shí)刻，因此需要對網(wǎng)頁變化頻率進(jìn)行估計(jì)。

目前，論壇爬蟲的研究還較少。文獻(xiàn)[6]研究了論壇抓取問題，它使用一組啟發(fā)式規(guī)則作為抓取策略，而在現(xiàn)實(shí)中存在數(shù)百種論壇結(jié)構(gòu)，無法為這些論壇制定一個(gè)普遍的啟發(fā)式規(guī)則。文獻(xiàn)[7]中提出了一種基于結(jié)構(gòu)化驅(qū)動(dòng)的爬蟲，通過人工選擇目標(biāo)頁面的一個(gè)樣本，使用該樣本頁面的DOM樹作為目標(biāo)的描述，但該爬蟲僅能找到通往目標(biāo)頁面的路徑，并不能找到最優(yōu)路徑。論壇中通常有多條路徑通往目標(biāo)頁面，這些路徑的大部分是快捷鏈接方式，不能涵蓋所有的目標(biāo)頁面。因此該方法并不適于論壇抓取。文獻(xiàn)[1-2]提出了智能化的論壇爬蟲IRbot，這種算法首先下載一些目標(biāo)論壇的樣本頁面，在樣本上構(gòu)建站點(diǎn)圖，在該圖上從全局角度考慮找到最優(yōu)遍歷路徑。該爬蟲與傳統(tǒng)爬蟲相比取得了較好的效果，但沒有能夠解決論壇的增量搜集問題。

3 相關(guān)定義

文獻(xiàn)[8]提出了基于信息生命周期的增量搜集技術(shù)，研究的是單個(gè)頁面中信息的變化規(guī)律。而在論壇中信息是跨越頁面的，信息的生命周期通過多個(gè)頁面表現(xiàn)，因而本文以屬于同一信息的頁面集合作為增量搜集的基本單位。

如圖1所示，論壇“軟件推薦”版塊的信息分布在27個(gè)帖子列表頁上，而其中第二個(gè)帖子的信息分布在5個(gè)帖子展示頁面上。每組頁面集合是一個(gè)信息整體，其中版塊指的是論壇中一個(gè)版塊所包含的頁面集合，帖子指的是論壇中一個(gè)帖子包含的頁面集合。

圖1 論壇網(wǎng)頁類型及版塊、帖子實(shí)例

最大抓取次數(shù)是指系統(tǒng)在現(xiàn)有的計(jì)算和帶寬資源下，單位時(shí)間段內(nèi)可提供的最大搜集次數(shù)。增量搜集需要保證本地?cái)?shù)據(jù)的時(shí)新性，本文使用延遲來表示數(shù)據(jù)的時(shí)新程度，下面給出版塊延遲和系統(tǒng)總延遲的定義。

定義1：給定一個(gè)版塊P，生成新的帖子的時(shí)間序列G為g1,g2,…,gk；有新回復(fù)帖子的時(shí)間序列R為r1,r2,…,rn。增量搜集系統(tǒng)對版塊P的增量搜集的時(shí)間序列C為c1,c2,…,cm。對于一個(gè)在gi時(shí)間產(chǎn)生的帖子Gi，它的延遲定義如下:

D(Gi)=cj-gi

(1)

其中cj是C中滿足gi≤cj條件的最小值。

同理，對于在ri時(shí)間新增的回復(fù)Ri，它的延遲定義如下：

D(Ri)=cj-ri

(2)

其中cj是C中滿足ri≤cj條件的最小值。

那么版塊P的延遲定義如下：

(3)

其中θ是調(diào)節(jié)參數(shù)，通常優(yōu)先獲取新增帖子比獲取新回復(fù)更加重要。

定義2：增量搜集系統(tǒng)需要抓取多個(gè)版塊，不同的版塊重要度不同，優(yōu)先減小重要度較大的版塊的延遲會(huì)獲得更好的效果。如果增量系統(tǒng)的目標(biāo)論壇包含的版塊為{P1,P2,…,Pn},并且每個(gè)版塊Pi擁有一個(gè)重要度Wi,那么系統(tǒng)總延遲定義如下：

(4)

4 基于版塊的增量搜集策略

基于版塊的增量搜集策略建立在大規(guī)模數(shù)據(jù)的基礎(chǔ)上，可以使用文獻(xiàn)[1-2]中的算法獲取數(shù)據(jù)，利用分頁鏈接將屬于同一版塊和同一帖子的頁面組織在一起。

本策略包含兩部分：基于版塊的增量抓取算法和增量調(diào)度算法。前者負(fù)責(zé)查找抓取新增和新回復(fù)的帖子，后者確定對版塊的抓取頻率和每次抓取的時(shí)間點(diǎn)。

4.1 基于版塊的增量抓取算法

觀察多個(gè)論壇結(jié)構(gòu)，發(fā)現(xiàn)如圖2所示帖子按照最后回復(fù)時(shí)間的先后順序排列。使用MDR/DEPTA[10-11]算法可從版塊頁面中抽取帖子記錄，通過判斷記錄中URL是否抓取和最后回復(fù)時(shí)間比較，得到所有新增和新回復(fù)的帖子。具體算法如下：

圖2 帖子排序特點(diǎn)的例子

算法BIC基于版塊的增量抓取算法

輸入：版塊P={p1,p2,…,pn}，pi指P的第i個(gè)頁面。

步驟：1) 按順序取出P中的一個(gè)頁面Pi，進(jìn)行抓取分析，抽取信息得到一組帖子記錄L。其中的每個(gè)記錄有兩個(gè)屬性：URL以及該帖子對應(yīng)的最后回復(fù)時(shí)間。

2) ForL中的每一項(xiàng)li(URL,last_reply_time)，判讀該帖子的URL是否存在本地索引庫LocalDB中。

Ifli.URL不在LocalDB中，那么這是一個(gè)新增的帖子。

Then 抓取該帖子存儲(chǔ)到本地資料庫中。

elseli.URL已經(jīng)存在于LocalDB中了，那么判斷最后回復(fù)時(shí)間是否更新。

If last_reply_time 已經(jīng)變化，那么說明該帖子有新回復(fù)。

Then 抓取該帖子新回復(fù)的部分存儲(chǔ)到LocalDB中。

Else 該帖子沒有任何變化，不做任何處理。

3) 循環(huán)步驟1)、2)，直至P中的某一頁pj，從中抽取出的帖子列表L中，沒有任何新增或新回復(fù)的帖子,算法停止。

4.2 基于版塊的增量調(diào)度算法

本節(jié)根據(jù)統(tǒng)計(jì)出的版塊的變化規(guī)律，提出了基于版塊的增量調(diào)度算法。算法分為兩部分：(1)根據(jù)版塊權(quán)重分配抓取次數(shù)，確定抓取頻率。(2)根據(jù)版塊的局部時(shí)間規(guī)律，確定針對版塊的抓取時(shí)間點(diǎn)。經(jīng)過調(diào)度使得系統(tǒng)的總延遲大幅減小。

4.2.1 論壇版塊變化規(guī)律的研究

啟動(dòng)論壇爬蟲，從2007-12-15到2009-03-30抓取了包括百度貼吧、舜網(wǎng)等17個(gè)論壇的數(shù)據(jù)，共有約108萬個(gè)帖子，定義為數(shù)據(jù)集Q。在數(shù)據(jù)集Q中，每個(gè)帖子表示為T={board,publish_time,r_time1,r_time2,...,r_timen}，board是指該帖子隸屬的版塊，publish_time是T的發(fā)布時(shí)間，而r_timei是指該帖子的第i個(gè)回復(fù)的時(shí)間，n是回復(fù)數(shù)目。版塊的變化次數(shù)就是其包含所有帖子的變化次數(shù)之和。

圖3展示的是百度貼吧中20個(gè)版塊的變化情況。不同版塊在一星期內(nèi)的變化次數(shù)分布如圖3(a)所示，不同版塊的變化次數(shù)相差較大。圖3(b)縱軸是指每小時(shí)內(nèi)變化次數(shù)與總變化次數(shù)的比值，各個(gè)版塊總的變化趨勢相同，在不同的時(shí)間點(diǎn)變化頻率相差很大。這說明版塊的變化頻率與一天內(nèi)的局部時(shí)間相關(guān)，定義為版塊的局部時(shí)間規(guī)律。這種現(xiàn)象與文獻(xiàn)[9]中統(tǒng)計(jì)的變化頻率較大的頁面的變化規(guī)律相似。

圖3 版塊在一星期和24小時(shí)內(nèi)的變化次數(shù)分布

4.2.2 分配抓取次數(shù)

如圖3(a)中的統(tǒng)計(jì)，不同的版塊的更新速度不同，而且不同版塊的重要度也不相同。版塊的權(quán)重與版塊的更新速度、版塊重要度以及論壇重要度有關(guān)，需要根據(jù)版塊權(quán)重確定對版塊的抓取頻率。版塊的權(quán)重定義如下：

WP=Ws×Wp×(Ng+θ×Nr)，

(5)

(0<θ≤1)

Ws是網(wǎng)站的重要性，Wp是版塊的重要性，Ng和Nr分別是該版塊中某段時(shí)間每天新增和新回復(fù)帖子數(shù)目的平均值，θ是調(diào)節(jié)參數(shù)。在本文中，暫不考慮論壇和版塊的重要度，Ws和Wp都設(shè)置為1。

假設(shè)有n個(gè)版塊，每個(gè)版塊Pi的權(quán)重為WPi,可使用的最大抓取次數(shù)為M,則分配給該版塊Pi的抓取次數(shù)定義如下：

×M

(6)

4.2.3 確定抓取時(shí)間點(diǎn)

圖3(b)反映出版塊的更新頻率具有局部時(shí)間規(guī)律，在8點(diǎn)到24點(diǎn)這個(gè)階段更新頻率較大，而從0點(diǎn)到8點(diǎn)的階段更新頻率大幅減小。因此需要根據(jù)版塊的局部時(shí)間規(guī)律以及分配給它的抓取次數(shù)m，確定m個(gè)抓取時(shí)間點(diǎn)，使得該版塊的延遲最小。

我們使用版塊P最近一段時(shí)間S中的數(shù)據(jù)，將帖子創(chuàng)建時(shí)間和回復(fù)時(shí)間按照時(shí)間粒度K分布在從0點(diǎn)到23點(diǎn)的范圍內(nèi)，這樣得到一組區(qū)間{T1,T2,…,Tk}，每個(gè)區(qū)間Ti都有一個(gè)分值SCi：

(7)

其中g(shù)_numi和r_numi分別是落在區(qū)間Ti中的帖子創(chuàng)建數(shù)目和回復(fù)數(shù)目。如下圖，K為1h。

如果分配給版塊P的抓取次數(shù)為m,根據(jù)版塊更新頻率的時(shí)間局部性規(guī)律來確定抓取時(shí)間點(diǎn)，有兩種方式：

(1) 假設(shè)采集時(shí)間點(diǎn)分別為c1,c2,…,cm，且函數(shù)f(t)表示為時(shí)間點(diǎn)為t時(shí)的SC值。那么版塊P的延遲D(P)為：

，

(8)

其中c0=0,cm+1=24。

圖4 版塊局部時(shí)間規(guī)律圖

等于零，得到如下公式：

(9)

由公式(9)可以看到ci+1采集點(diǎn)可以直接根據(jù)公式由ci和ci-1點(diǎn)確定。但在這種方式中，c1點(diǎn)的確定需要由人工指定，而c1點(diǎn)的選取直接確定了其他采集點(diǎn)的選取。

(2) 在上面的方式中c1無法確定且計(jì)算復(fù)雜，可以使用如下的近似算法：將圖4中矩形塊組成的區(qū)域等分為m+1塊，每個(gè)分割點(diǎn)就是確定的抓取時(shí)間點(diǎn)。這樣在更新頻率較高的時(shí)間段，分配的抓取點(diǎn)也較多。這種方式是近似最小延遲，但簡單易于計(jì)算。

算法BRA基于版塊的增量調(diào)度算法

輸入：所有版塊對應(yīng)的權(quán)重集合為WP={wp1,wp2,…,wpn}，局部時(shí)間規(guī)律集合SC={sc1,sc2,…,scn},其中sci是一個(gè)24維的數(shù)組。單位時(shí)間的最大抓取次數(shù)為M。

輸出：每個(gè)版塊Pi的抓取時(shí)間點(diǎn)集合Ci{c1,c2,…,cmi}。

步驟：1) 任取WP中未處理的wpi,根據(jù)公式(6)計(jì)算分配給版塊Pi的抓取次數(shù)mi。

2) 計(jì)算等分塊的面積A=1/(mi+1),累計(jì)面積SA=0;并取出Pi對應(yīng)的數(shù)組sci。

Forjfrom 1 to 24

If SA>=A時(shí)

計(jì)算抓取時(shí)間點(diǎn)ci

并將ci加入到集合Ci中;A+=1/(mi+1);

Else SA+=sci[j];

3) 輸出所有的抓取時(shí)間點(diǎn)集合C1,C2,…Cn。

5 實(shí)驗(yàn)和結(jié)果

5.1 實(shí)驗(yàn)準(zhǔn)備

從表1中展示的八個(gè)網(wǎng)站中選取的110多個(gè)版塊，選擇發(fā)布或回復(fù)時(shí)間在2009年1月初到2009年6月底期間的帖子進(jìn)行抓取，共得到138 258個(gè)帖子。定義為數(shù)據(jù)集S。

表1 實(shí)驗(yàn)中抓取的論壇

在確定版塊抓取頻率和抓取時(shí)間點(diǎn)時(shí)都需要利用版塊的統(tǒng)計(jì)信息，需要確定統(tǒng)計(jì)的時(shí)間范圍。經(jīng)過實(shí)驗(yàn)發(fā)現(xiàn)統(tǒng)計(jì)范圍從20天開始估算出的權(quán)重和局部時(shí)間規(guī)律趨于穩(wěn)定。

5.2 評測基于版塊的增量搜集策略

5.2.1 評測增量抓取算法

為了評估增量搜集算法的質(zhì)量，我們使用兩個(gè)評測標(biāo)準(zhǔn)召回率和準(zhǔn)確率：

圖5 召回率和準(zhǔn)確率

本文提出的基于版塊的增量抓取算法BIC。算法EIC以帖子和版塊的平均變化間隔計(jì)算帖子的下次變化時(shí)間和新增帖子的出現(xiàn)時(shí)間。在數(shù)據(jù)集S上進(jìn)行模擬抓取實(shí)驗(yàn)，6小時(shí)為一個(gè)抓取周期，持續(xù)時(shí)間從5月25日到6月25日共31天。計(jì)算每天兩個(gè)評測標(biāo)準(zhǔn)的平均值，兩種算法的比較結(jié)果如圖5所示。從結(jié)果看，BIC算法在召回率和準(zhǔn)確率上均優(yōu)于算法EIC。EIC使用歷史平均變化頻率來估計(jì)變化時(shí)間，而帖子不同于普通頁面，變化頻率不能簡單的由歷史平均變化頻率來估計(jì)，因而EIC算法的準(zhǔn)確率很低。BIC算法通過判斷帖子的URL是否抓取以及最后回復(fù)時(shí)間是否變化，能保證所有抓取的帖子都是新增或發(fā)生變化的。準(zhǔn)確率高則可以避免重新抓取未變化的帖子，從而節(jié)省大量帶寬資源。

5.2.2 評測增量調(diào)度算法

以總延遲做為評測標(biāo)準(zhǔn)，我們在數(shù)據(jù)集S上進(jìn)行模擬抓?。簭臄?shù)據(jù)集S中可以得一組gij，rij序列,分別代表第i個(gè)版塊第j次發(fā)布帖子的時(shí)間和第j次回復(fù)的時(shí)間。根據(jù)計(jì)算出的權(quán)重和局部時(shí)間規(guī)律，確定了抓取時(shí)間序列cij。根據(jù)公式(4)，就可以算出總延遲。

為了說明調(diào)度算法具備普遍性，分別選取了4月5日—4月15日、5月10日—5月20日、6月15日—6月25日，三段周期為10天的區(qū)間，每天采集次數(shù)m={4,5,…,11}次，根據(jù)該日期前20天的數(shù)據(jù)來計(jì)算版塊權(quán)重和局部時(shí)間規(guī)律，計(jì)算權(quán)重時(shí)θ設(shè)置為0.5且區(qū)間粒度設(shè)置為1小時(shí)。分別采用下面四種調(diào)度方式：

ERA.按照版塊平均分配抓取次數(shù)和按照時(shí)間平均確定采集時(shí)間點(diǎn)的方式。

WRA.只按照統(tǒng)計(jì)出的版塊權(quán)重權(quán)重進(jìn)行調(diào)度。

LRA.只按照局部時(shí)間規(guī)律確定抓取時(shí)間點(diǎn)。

BRA.按照統(tǒng)計(jì)的權(quán)重和局部時(shí)間規(guī)律進(jìn)行調(diào)度和確定抓取時(shí)間點(diǎn)。

計(jì)算出的總延遲的結(jié)果如圖6所示。

圖6 三個(gè)不同時(shí)間段的總延遲結(jié)果

圖6縱軸是總延遲的日平均值，其中ERA的延遲并非單調(diào)遞減的，增加抓取次數(shù)，延遲反而增大，這是沒有考慮版塊局部時(shí)間規(guī)律的緣故，這種進(jìn)一步說明了局部時(shí)間規(guī)律的重要性。從圖6可以看出，在總資源耗費(fèi)相同的情況下，在三個(gè)時(shí)間區(qū)間內(nèi)，我們提出的基于版塊的增量調(diào)度算法BRA的總延遲最低。

將三個(gè)時(shí)間段中算法ERA和算法BRA求出的總延遲求平均值，計(jì)算算法BRA在總延遲上減小的比例，如表2所示。

表2 與基準(zhǔn)方法比較

根據(jù)表2中的數(shù)據(jù)，相對基準(zhǔn)ERA方法，本文提出的BRA算法最高減小了42%的延遲。

6 結(jié)論及將來的工作

本文通過分析多個(gè)論壇的結(jié)構(gòu)和變化規(guī)律，發(fā)現(xiàn)新增和新回復(fù)帖子通常按時(shí)間順序排列，不同的版塊更新速度不同并且版塊的更新頻率與當(dāng)天的局部時(shí)間相關(guān)。據(jù)此提出了一種新的基于版塊的論壇增量搜集策略，以同一信息包含的頁面集合為調(diào)度單位。策略包括增量抓取算法和調(diào)度算法，實(shí)驗(yàn)結(jié)果顯示，本策略能在保證很高的覆蓋率和準(zhǔn)確率的同時(shí)，大幅減小系統(tǒng)的總延遲。存在一些BBS式的論壇，其版塊頁面不展示帖子的最后回復(fù)時(shí)間等信息，無法判斷帖子是否發(fā)生變化。針對這種情況，下一步的工作是研究帖子的變化規(guī)律，預(yù)測下次回復(fù)的時(shí)間，解決及時(shí)獲取新回復(fù)的問題。

[1] Cai R, Yang JM, Lai W., et al. iRobot: An Intelligent Crawler for Web Forums[C]//Proc. of the 17th World Wide Web Conf.Beijing,2008:447-456.

[2] Wang Y, Yang JM, Lai W,et al. Exploring Traversal Strategy for Web Forum Crawling[C]//ACM SIGIR. Singapore,2008: 459-466.

[3] Cho J, Garcia-Molina H. The evolution of the Web and implications for an incremental crawler[C]//Proc. of the 26th Int’l Conf. on Very Large Databases. San Francisco: Morgan Kaufmann Publishers, 2000: 200-209.

[4] 孟濤,王繼民, 閆宏飛.網(wǎng)頁變化與增量搜集技術(shù)[J].軟件學(xué)報(bào), 2006,17(5):1051-1067

[5] Cho J, Garcia-Molina H. Effective page refresh policies for Web crawlers[J]. ACM Trans. on Database Systems, 2003,28(4): 390-426.

[6] Guo Y, Li K, Zhang K, et al. Board forum crawling: a Web crawling method for Web forum[C]//Proc. 2006 IEEE/WIC/ACM Int.Conf.Web Intelligence, Hong Kong, 2006：745-748.

[7] M. L. A. Vidal, A. S. Silva, E. S. Moura, and J. M. B. Caval-canti. Structure-driven crawler generation by example[C]//Proc. of the 29th SIGIR Conf,Seattle,2006：292-299.

[8] Olston, C. and Pandey, S. Recrawl scheduling based on information longevity[C]//Proc. of the 17th World Wide Web Conf. New York,2008：437-446.

[9] S. O’Brien and C.Grimes.Microscale evolution of web pages[C]//Proceedings of the 17th International World Wide Web Conf, New York,2008：1149-1150.

[10] Liu B, Grossman, R and Zhai, Y. Mining data records from Web pages[C]//Proc. of the 9th ACM SIGKDD Int’l Conf. on Knowledge discovery and data mining,Washington, 2003：601-606.

[11] Zhai Y , Liu B. Structured data extraction from the Web based on partial tree alignment[J]. IEEE Trans. Knowl. Data Eng. 2006,18(12):1614-1628.

[12] Cho J, Ntoulas A. Effective change detection using sampling[C]//Proc. of the 28th Int’l Conf. on Very Large Databases. San Francisco: Morgan Kaufmann Publishers, 2002：514-525.