李永鋒，王惠臨

（中國(guó)科學(xué)技術(shù)信息研究所，北京100038）

0 引 言

隨著新聞組和RSS等信息聚合的發(fā)展，基于內(nèi)容的發(fā)布/訂閱系統(tǒng)得到廣泛重視，RSS是Web 2.0的重要內(nèi)容之一，同時(shí)也給發(fā)布/訂閱系統(tǒng)提出了許多挑戰(zhàn)。信息資源越來(lái)越豐富，而人們所需要信息是有限的，人們接收和處理信息能力也是有限的，導(dǎo)致了發(fā)布/訂閱范型的產(chǎn)生。這種系統(tǒng)能夠很好地支持有選擇的消息分發(fā)，從海量的信息中，例如時(shí)事報(bào)道，電子圖書，網(wǎng)絡(luò)廣告，股票報(bào)價(jià)，天氣預(yù)報(bào)消息等等，為用戶提供個(gè)性化的內(nèi)容遞送。發(fā)布/訂閱是一種異步的通信范型，用戶訂閱消息，當(dāng)有符合條件的消息發(fā)布時(shí)，系統(tǒng)通知用戶。發(fā)布訂閱平臺(tái)為新發(fā)布的消息尋找相匹配的訂閱，然后把該消息轉(zhuǎn)發(fā)訂閱者。同一用戶可以同時(shí)是發(fā)布者和訂閱者。

早期用戶通過(guò)預(yù)先定義好主題發(fā)布和訂閱事件，NNTP新聞組就是這類基于主題的發(fā)布/訂閱系統(tǒng)的代表。通過(guò)主題來(lái)分類事件的方式過(guò)于粗糙，用戶經(jīng)常收到冗余的數(shù)據(jù)，雖然這些數(shù)據(jù)屬于訂閱的主題。最新的系統(tǒng)是基于內(nèi)容的。在基于內(nèi)容的系統(tǒng)中，用戶可以直接對(duì)事件的內(nèi)容形式做限制，從而獲取精確的信息。

隨著網(wǎng)絡(luò)資源的迅速增加，人們需要對(duì)這些海量的網(wǎng)絡(luò)資源進(jìn)行有效地管理。元數(shù)據(jù)是管理這些資源的有效方法。元數(shù)據(jù)是 “關(guān)于數(shù)據(jù)的數(shù)據(jù)”或者 “關(guān)于信息的信息”。一個(gè)資源的元數(shù)據(jù)被認(rèn)為是這個(gè)資源的語(yǔ)意。元數(shù)據(jù)是保證這些資源在未來(lái)能夠容易被使用的關(guān)鍵。應(yīng)用最廣泛的元數(shù)據(jù)標(biāo)準(zhǔn)有Dublin Core［2］和 MARC［12］等等。針對(duì)元數(shù)據(jù)的發(fā)布/訂閱系統(tǒng)為管理各種資源的內(nèi)容提供有效的能力。例如，在網(wǎng)上書店，一個(gè)用戶可以通過(guò)對(duì)電子文檔的元數(shù)據(jù)的限制來(lái)訂閱電子文檔，例如 “title＝ ‘Green on Greens’＆coverage＝ ‘17thcentury’”，當(dāng)書店的進(jìn)貨包括這樣的文檔內(nèi)容的時(shí)候，系統(tǒng)就準(zhǔn)確通知用戶。

需要注意的是，發(fā)布/訂閱系統(tǒng)與數(shù)據(jù)庫(kù)查詢的區(qū)別。傳統(tǒng)的數(shù)據(jù)庫(kù)為這些場(chǎng)景設(shè)計(jì)的：數(shù)據(jù)庫(kù)中已經(jīng)保存有大量的數(shù)據(jù)，用戶可以通過(guò)設(shè)置查詢條件 （例如用SQL語(yǔ)句）去尋找需要的數(shù)據(jù)。但是發(fā)布/訂閱范型剛好反過(guò)來(lái)，系統(tǒng)中保存的是大量的用戶訂閱 （類似于查詢條件），數(shù)據(jù)流入系統(tǒng)和訂閱相匹配，如果匹配，則通知訂閱者。

這篇論文的主要貢獻(xiàn)如下：

（1）本文設(shè)計(jì)了新穎的索引結(jié)構(gòu)對(duì)訂閱進(jìn)行分組索引，消除了一個(gè)訂閱因?yàn)榘鄠€(gè)謂詞而造成的多次索引、計(jì)數(shù)和比較。

（2）我們?cè)O(shè)計(jì)了新的基于分組的過(guò)濾算法，該算法通過(guò)緩存謂詞匹配結(jié)果使得謂詞匹配結(jié)果得以在訂閱過(guò)濾過(guò)程中傳播，取得了很高的過(guò)濾性能。

（3）通過(guò)全面的實(shí)驗(yàn)，以及對(duì)算法詳細(xì)的空間時(shí)間復(fù)雜度分析，證明了算法的有效性。實(shí)驗(yàn)表明，我們的系統(tǒng)可以有效處理達(dá)上百萬(wàn)訂閱的工作量。同時(shí)，實(shí)驗(yàn)中通過(guò)提取詞干和消除停用詞，極大提高系統(tǒng)的查全率和精度。

1 相關(guān)工作

早期的發(fā)布/訂閱系統(tǒng)是基于主題的，廣泛應(yīng)用的有Network News Transfer Protocol［11］，IBM 的 MQSeries［4］，google 的 google reader［9］， 和 Microsoft 的 Biz Talk Server［6］?，F(xiàn)在基于主題的發(fā)布/訂閱系統(tǒng)方面的研究，主要集中在 P2P環(huán)境下［8］。

基于內(nèi)容的發(fā)布/訂閱系統(tǒng)允許過(guò)濾消息內(nèi)容。基于內(nèi)容的過(guò)濾使用戶可以精確表達(dá)個(gè)性化要求。公開(kāi)發(fā)表的文獻(xiàn)中提出了不少關(guān)于內(nèi)容的過(guò)濾算法。結(jié)合幾種數(shù)據(jù)結(jié)構(gòu)，使用針對(duì)應(yīng)用的緩存，針對(duì)應(yīng)用的查詢處理，系統(tǒng)［3］可以達(dá)到很高的負(fù)載和速度。在文獻(xiàn) ［1］中，系統(tǒng)設(shè)計(jì)用來(lái)根據(jù)XPath或XQuery表達(dá)式去過(guò)濾XML文件。XPath可以用來(lái)描述一棵樹(shù)結(jié)構(gòu)的路徑模式，但是路徑模式不允許進(jìn)一步用關(guān)系算子進(jìn)行限制，而這個(gè)在我們的系統(tǒng)中已經(jīng)其它非XML系統(tǒng)中是可以做到的。Tai［7］把語(yǔ)意引進(jìn)了發(fā)布/訂閱系統(tǒng)。OPS［10］是一個(gè)基于本體的發(fā)布/訂閱系統(tǒng)，系統(tǒng)中的事件和訂閱都用RDF圖來(lái)表示。Keidl［5］提出了一個(gè)分布式元數(shù)據(jù)系統(tǒng)，它是在關(guān)系數(shù)據(jù)庫(kù)上實(shí)現(xiàn)的，但是不能擴(kuò)展到上百萬(wàn)個(gè)訂閱的情形或者很高事件吞吐量的情形。

2 數(shù)據(jù)模型

元數(shù)據(jù)是機(jī)器可以理解的信息。它是 “關(guān)于數(shù)據(jù)的數(shù)據(jù)”。總的來(lái)說(shuō)，元數(shù)據(jù)用來(lái)描述別的數(shù)據(jù)的集合，這個(gè)集合稱為資源。元數(shù)據(jù)抓住了資源最重要的信息，例如資源怎么收集的和怎么處理的，使得以后的用戶能夠理解這些細(xì)節(jié)。從這種意義上說(shuō)，元數(shù)據(jù)是保證資源在未來(lái)繼續(xù)存在的關(guān)鍵。元數(shù)據(jù)很有用。在搜索系統(tǒng)中，元數(shù)據(jù)使得用戶能快速定位自己需要的數(shù)據(jù)。用元數(shù)據(jù)的查詢可以使用戶省去大量人工的復(fù)雜的過(guò)濾操作。試想這樣一個(gè)場(chǎng)景，如果沒(méi)有我們?cè)噲D在沒(méi)有書目管理和電腦查詢系統(tǒng)輔助的圖書館查找一本書有多困難。在數(shù)目和電腦查詢系統(tǒng)里面存有的信息本質(zhì)上就是關(guān)于這些書的元數(shù)據(jù)。在我們的系統(tǒng)中，元數(shù)據(jù)是作為發(fā)布語(yǔ)言。應(yīng)用最廣泛的元數(shù)據(jù)標(biāo)準(zhǔn)有Dublin Core和MARC。本文實(shí)驗(yàn)采用的是Dublin Core標(biāo)準(zhǔn)。

從這些標(biāo)準(zhǔn)中抽象出來(lái)，在我們的系統(tǒng)中，一個(gè)事件表示為二元組 （域，數(shù)據(jù)項(xiàng)組）的集合，其中屬性有唯一的屬性名，數(shù)據(jù)項(xiàng)組可以有一個(gè)或多個(gè)數(shù)據(jù)組成。屬性包含三類，一是數(shù)值型的，一類是字符型的，一類是分類型的。這里說(shuō)明一下分類型屬性，分類型屬性用來(lái)描述層次結(jié)構(gòu)，這一點(diǎn)在元數(shù)據(jù)中很常見(jiàn)。分類的域是枚舉類型的，域中的元素被組織成層次結(jié)構(gòu)，例如在一個(gè)學(xué)校的圖書館，根據(jù)主題書籍可以分為哲學(xué)，歷史，技術(shù)等等種類，其中歷史又可以分為通用的，歐洲的，亞洲和非洲等等子種類。我們把事件集合中的一個(gè)元素叫做一個(gè)段。例如，｛（Title，“A Guide to Growing Roses”）， （description， “Describes process for planting and nurturing different kinds of rose bushes”），（date，“2001—01—20”），（format，“image”）｝就是一個(gè)簡(jiǎn)單的事件。其中 （format，“image”）就是一個(gè)段。

一個(gè)訂閱是三元組 （屬性，算符，關(guān)鍵字?jǐn)?shù)組）的集合，其中對(duì)于值為字符類型的屬性來(lái)說(shuō)，算符只有，表示包含，對(duì)于值為數(shù)值型的屬性，算符可以為＜，＞及＝，表示通常意義下的數(shù)學(xué)關(guān)系語(yǔ)意。在現(xiàn)實(shí)應(yīng)用中，訂閱的三元組集合的大小不會(huì)超過(guò)5。和搜索系統(tǒng)類似的，訂閱是用來(lái)限制事件的各個(gè)屬性及其取值。例如， （title，，“Harry Potter”）∧ （year，＞，2000）就是一個(gè)常見(jiàn)的訂閱。在以下，我們把訂閱中的一個(gè)三元組叫做一個(gè)謂詞。

為了確定事件和訂閱之間的關(guān)系，我們給出以下定義：

謂詞匹配：給定一個(gè)謂詞p＝ （attributei，opi，valuei）和一個(gè)段s＝ （attributej，setjof values），s匹配p當(dāng)且僅當(dāng)①attributei＝attributej，并且②對(duì)于valuei，s中存在valuej∈setjof values，使得valuejopivaluei成立。

例1：段 （year，2006）滿足謂詞 （year，＞，2000）。因?yàn)?“year”＝ “year”并且2006＞2000。

訂閱匹配：給定一個(gè)訂閱s＝p1∧p2∧……∧pn，和一個(gè)事件e＝ ｛seg1，seg2，……，segm｝，e匹配s當(dāng)且僅當(dāng)對(duì)于s中的任意pi，e中存在segj使得segj滿足pi。

例2：事件 ｛（Title，“Harry Potter and the chamber of secrets”），（year，2006）， （creator， “J.K.ROWLING”）｝匹配訂閱 （title，contains，“Potter”）∧ （year，＞，2000）。

3 過(guò)濾算法

在發(fā)布/訂閱系統(tǒng)中，核心的一個(gè)問(wèn)題就是如何有效的把數(shù)據(jù)流和訂閱匹配。這個(gè)問(wèn)題定義如下：

過(guò)濾過(guò)程：給定訂閱集合D＝ ｛s1，s2，……，sn｝，當(dāng)一個(gè)元數(shù)據(jù)e流入的時(shí)候，返回匹配的訂閱集合Ds＝｛si｜e滿足si，si∈D｝。

3.1 未分組過(guò)濾算法

為了找到所有符合的訂閱，最直觀的方法是每到一個(gè)事件，把它和系統(tǒng)中的每個(gè)用戶訂閱進(jìn)行比較。這種方法在訂閱數(shù)量很大的時(shí)候，開(kāi)銷是很大的。最壞的情況，這種算法的時(shí)間復(fù)雜度為其中Cp代表匹配一個(gè)謂詞的時(shí)間開(kāi)銷。這種方法并沒(méi)有考慮系統(tǒng)中訂閱的謂詞間的依存關(guān)系。例如，如果1000個(gè)訂閱都包含有一個(gè)相同的謂詞，這個(gè)系統(tǒng)并不知道這個(gè)信息，所以對(duì)這個(gè)謂詞將評(píng)估1000次。

所以，應(yīng)該把訂閱中相同的謂詞考慮進(jìn)去。我們把各個(gè)不同謂詞作為訂閱的索引。當(dāng)系統(tǒng)中含相同謂詞的訂閱很多的時(shí)候，這個(gè)方法可以節(jié)省大量的比較時(shí)間，因?yàn)樗苊饬藢?duì)一個(gè)相同謂詞的重復(fù)評(píng)估。我們把這個(gè)方法叫做未分組過(guò)濾算法。下面我們用e代表新來(lái)的一個(gè)事件。用matchingPred保存和事件e相匹配的謂詞。用matching－Subs保存和e相匹配的訂閱。下面描述這個(gè)算法，以便和我們后面的算法對(duì)比。

未分組過(guò)濾算法：match（e）

輸入：事件e＝ ｛（attribute1，set1of values），…… ，（attributen，setnof values）｝

輸出：候選匹配訂閱集合matchingSubs

（1）matchingPred←

（2）matchingSubs←

（3）循環(huán) 對(duì)每個(gè)屬性attributei∈e

（4） 循環(huán) 對(duì)每個(gè)值v∈setiof values

（5） matchingPreds← matchingPreds＋ Pi.search （v）

（6）循環(huán) 對(duì)于每個(gè)p∈matchingPreds

（7） 循環(huán)對(duì)于每個(gè)s∈pred＿to＿subs［p］

（8） s.count＋ ＋

（9）循環(huán) 對(duì)于系統(tǒng)中的每個(gè)s

（10） 如果s.count＝＝s.nb＿pred則 matching Subs←matchingSubs∪ ｛s｝

（11）返回matchingSubs

未分組過(guò)濾算法可以大概分為兩步。第一步，算法從索引結(jié)構(gòu)中查找所有和事件e匹配的謂詞。第二步對(duì)和這些匹配的謂詞相關(guān)的訂閱進(jìn)行驗(yàn)證。時(shí)間開(kāi)銷也分為謂詞匹配時(shí)間和訂閱匹配時(shí)間兩部分組成。算法的時(shí)間復(fù)雜度其中Csearch在索引中找一個(gè)關(guān)鍵詞的平均時(shí)間代表事件中屬性的總個(gè)數(shù)，Nval代表事件中單個(gè)屬性關(guān)鍵字的平均個(gè)數(shù)，Cadd是作一次加法計(jì)數(shù)的開(kāi)銷，Psat是和事件e相匹配的謂詞的集合，Np是每個(gè)訂閱滿足要求的謂詞的平均數(shù)目，Ccomp是比較一次的時(shí)間，而代表系統(tǒng)中訂閱的總數(shù)。

未分組過(guò)濾算法的空間開(kāi)銷主要有索引，指針鏈表和訂閱。諸如Trie，AVL和B樹(shù)等索引結(jié)構(gòu)的空間復(fù)雜度不會(huì)超過(guò)系統(tǒng)中不同謂詞的數(shù)目。索引結(jié)構(gòu)中的指針鏈表的大小和謂詞的總數(shù)相等。而且，每個(gè)訂閱只在一個(gè)地方存放。所以空間復(fù)雜度是和系統(tǒng)中謂詞的數(shù)量成正比的。

3.2 基于分組的傳播過(guò)濾算法

相對(duì)于直觀的方法，未分組過(guò)濾算法取得了很大的進(jìn)步。但是我們進(jìn)一步分析可以發(fā)現(xiàn)，過(guò)濾時(shí)間的很大一部分是消耗在對(duì)謂詞的計(jì)數(shù)上了。我們可以通過(guò)限制需要驗(yàn)證的訂閱的數(shù)目來(lái)減少這個(gè)時(shí)間。我們其實(shí)不必要對(duì)訂閱中的每個(gè)謂詞都索引，我們只需在每個(gè)訂閱中選擇其中一個(gè)最不常用的謂詞對(duì)訂閱進(jìn)行分組索引。只有該謂詞符合新來(lái)的發(fā)布事件的時(shí)候，這個(gè)訂閱的其它謂詞才需要被進(jìn)一步驗(yàn)證。索引結(jié)構(gòu)如圖1所示。為了加快剩余謂詞的驗(yàn)證速度，我們?yōu)樾聛?lái)的事件建立一個(gè)謂詞匹配結(jié)果位串，用來(lái)記錄謂詞的驗(yàn)證結(jié)果，每個(gè)謂詞對(duì)應(yīng)其中的一位，以下用pred＿map標(biāo)識(shí)。初始時(shí)，所有pred＿map位為0，當(dāng)有新事件流入的時(shí)候，匹配好的謂詞對(duì)應(yīng)在pred＿map中的位置1，其它為0。在驗(yàn)證整個(gè)訂閱到時(shí)候，我們通過(guò)pred＿to＿group，從pred＿map為1的單元反向找到訂閱，這個(gè)謂詞是已經(jīng)被驗(yàn)證過(guò)的，這些訂閱可能和事件相匹配。這些訂閱根據(jù)謂詞的數(shù)目進(jìn)行分組，以加快匹配速度，同一組的訂閱具有相同數(shù)目的謂詞。

圖1 基于分組的訂閱索引結(jié)構(gòu)

基于分組的傳播過(guò)濾算法match（e）：

輸入：事件e＝ ｛（attribute1，set1of values），……，（attributen，setnof values）｝

輸出：候選匹配訂閱集合matchingSubs

（1）matchingPred←

（2）matchingSubs←

（3）循環(huán) 對(duì)每個(gè)屬性attributei∈e

（4） 循環(huán) 對(duì)每個(gè)值v∈setiof values

（5） matchingPreds← matchingPreds＋Pi.search （v）

（6）循環(huán) 對(duì)于系統(tǒng)中的每個(gè)謂詞p

（7） 如果p∈matchingPreds則pred＿map［p］＝1否則pred＿map［p］＝0

（8）循環(huán) 對(duì)于每個(gè)p∈matchingPreds

（9） 循環(huán) 對(duì)每個(gè)家族fi∈pred＿to＿group［p］

（10） 循環(huán)j＝1 to i

（11） buf←

（12） 循環(huán) 對(duì)于每個(gè)s∈fi

（13） 如果pred＿map ［s.predj］＝＝1則buf←buf∪s

（14） fi←buf

（15） matchingSubs←matchingSubs＋fi

（16）返回matchingSubs

基于分組的傳播過(guò)濾算法包括謂詞驗(yàn)證和訂閱匹配。算法的時(shí)間復(fù)雜度為Nval＋CreadbPsatNsv），其中Csearch代表在索引結(jié)構(gòu)中查詢一個(gè)關(guān)鍵字的平均時(shí)間開(kāi)銷，是事件中屬性的總數(shù)，Nval代表事件中每個(gè)屬性關(guān)鍵字的平均數(shù)目，Csetb代表在pred＿map設(shè)置一個(gè)標(biāo)志位的時(shí)間，Creadb是驗(yàn)證pred＿map一位的時(shí)間，Psat是和事件匹配的所有謂詞，Nsv是在比較中驗(yàn)證的平均謂詞數(shù)目。

基于分組的傳播過(guò)濾算法的空間開(kāi)銷主要有索引結(jié)構(gòu)，指針鏈表和訂閱幾部分所組成。諸如Trie，AVL，B＋樹(shù)的索引結(jié)構(gòu)空間開(kāi)銷都不會(huì)超過(guò)系統(tǒng)中不同謂詞的總數(shù)。對(duì)比未分組過(guò)濾算法，指針鏈表的大小和系統(tǒng)中訂閱的數(shù)量相同，而未分組過(guò)濾算法和系統(tǒng)中謂詞的總數(shù)相同。pred＿map的大小是和系統(tǒng)中不同謂詞的數(shù)目一樣多的。而且，每個(gè)訂閱只需要一個(gè)存儲(chǔ)單元，所以整個(gè)系統(tǒng)的空間復(fù)雜度和系統(tǒng)中謂詞的大小成正比。

3.3 提取詞干和消除停用詞

元數(shù)據(jù)經(jīng)常包含自然語(yǔ)言來(lái)描述資源。例如，Dublin Core元數(shù)據(jù)標(biāo)準(zhǔn)推薦了15域用來(lái)描述一個(gè)資源，MARC也包含了諸多域表示資源的不同屬性例如作者，出版信息等。經(jīng)常出現(xiàn)這種情況，用戶訂閱中出現(xiàn)一個(gè)詞，但是在事件中沒(méi)有這個(gè)詞，而是這個(gè)詞的其它形式。比如說(shuō)英文里面的復(fù)數(shù)，動(dòng)名詞，過(guò)去式都是語(yǔ)法變化的例子，這些變化阻礙了訂閱和事件之間的匹配。為了部分解決這個(gè)問(wèn)題，我們用這些詞的詞干來(lái)代替這些詞，詞干就是消除這些詞的前后詞綴后留下的部分。例如cook就是一個(gè)詞干，它從cooker，cooking，cooked，和cooks中提取出來(lái)。詞干提取對(duì)于提高過(guò)濾算法的性能是有好處的，因?yàn)樗鼈儼岩粋€(gè)詞的多種形式合為一個(gè)。而且，提取詞干可以減少索引結(jié)構(gòu)的差距，因?yàn)橛邢嗤~干的詞被一個(gè)詞干所代表了。提取詞干可以大大提高系統(tǒng)的查全率。

我們注意到，在訂閱和事件中太常出現(xiàn)的詞，往往沒(méi)有什么區(qū)分度。事實(shí)上，如果一個(gè)詞在80%以上的訂閱和事件中出現(xiàn)的話，它對(duì)于過(guò)濾是沒(méi)有用的。這樣的詞叫停用詞。我們不把停用詞當(dāng)作索引關(guān)鍵字。比如說(shuō)漢語(yǔ)中的“的”，“了”，“是”等等，英語(yǔ)中的冠詞，介詞以及連詞都是停用詞的候選。消除停用詞可以減少索引結(jié)構(gòu)的大小，而不影響過(guò)濾精度。

我們對(duì)詞干的提取和停用詞的消除是在一個(gè)新的事件發(fā)布或者一個(gè)新的訂閱進(jìn)入系統(tǒng)的時(shí)候進(jìn)行的。在基于分組的傳播過(guò)濾算法中，提取詞干和消除停用詞會(huì)影響pred＿map數(shù)組，因?yàn)橛嗛喼械脑~變化的時(shí)候，必然引起謂詞的變化。

提取詞干算法：stemming（e）

輸入：一個(gè)訂閱s或者一個(gè)事件e

輸出：s或者e的詞干

（1）循環(huán) 對(duì)每個(gè)itemi∈s或者e

（2） 如果itemi是字符型屬性的值

（3） 則用取itemi的詞干代替它

（4）返回s或者e的詞干

消除停用詞算法：stopper（e）

輸入：一個(gè)訂閱s或者一個(gè)事件e

輸出：s或者e的詞干

（1）循環(huán) 對(duì)每個(gè)itemi∈s或者e

（2） 如果itemi是字符型屬性的值并且itemi是個(gè)停用詞

（3） 則從e或者s中刪除itemi

（4）返回不再有停用詞的s或者e

4 實(shí)驗(yàn)評(píng)估

在這一節(jié)，我們通過(guò)實(shí)驗(yàn)驗(yàn)證算法的性能。我們的實(shí)驗(yàn)是在一個(gè)單CPU的PC上進(jìn)行的，CPU是頻率為3.2GHz的Xeon芯片，內(nèi)存為4G，操作系統(tǒng)是Redhat Linux AS 4.0。未分組的過(guò)濾系統(tǒng)和基于分組的傳播系統(tǒng)都是用c＋＋語(yǔ)言在visual studio 2005環(huán)境下開(kāi)發(fā)的。在以下我們對(duì)實(shí)驗(yàn)的主要參數(shù)做一些規(guī)定，我們用AT表示訂閱中屬性的平均個(gè)數(shù)，用KW表示屬性中關(guān)鍵字的平均個(gè)數(shù)。實(shí)驗(yàn)中的事件是以Dublin Core元數(shù)據(jù)標(biāo)準(zhǔn)生成的，每個(gè)元數(shù)據(jù)有15個(gè)基本元素構(gòu)成。在下面的圖形中，過(guò)濾時(shí)間是指過(guò)濾1000個(gè)事件的總時(shí)間，時(shí)間單位是微秒。實(shí)驗(yàn)最大訂閱數(shù)為100萬(wàn)。

圖2到圖5表明在參數(shù)AT和KW設(shè)置到不同時(shí)，工作負(fù)載從10萬(wàn)增加到100萬(wàn)時(shí)，過(guò)濾算法的時(shí)間開(kāi)銷。不難看出，兩個(gè)算法都深受訂閱數(shù)目的影響，同時(shí)AT和KW對(duì)算法的影響是很明顯的。但是，未分組過(guò)濾算法對(duì)工作負(fù)載的敏感度大于基于分組的傳播過(guò)濾算法。基于分組的傳播過(guò)濾算法對(duì)于訂閱數(shù)目的增加，過(guò)濾時(shí)間基本上能保持線性增長(zhǎng)，而未分組過(guò)濾算法卻幾乎成指數(shù)增長(zhǎng)，當(dāng)訂閱數(shù)達(dá)到50萬(wàn)時(shí)候，未分組過(guò)濾算法的性能開(kāi)始急劇下降，而基于分組的傳播過(guò)濾算法還能保持線性增長(zhǎng)水平。當(dāng)系統(tǒng)中有100萬(wàn)個(gè)訂閱，AT＝4且KW＝2時(shí)，基于分組的傳播過(guò)濾算法平均每秒鐘處理1621個(gè)事件，而未分組過(guò)濾算法平均僅僅能夠處理1.1個(gè)事件。圖6和圖7主要對(duì)比在引進(jìn)詞干提取和取消停用詞和不引進(jìn)之間的性能差。詞干提取和取消停用詞技術(shù)不但能夠提高過(guò)濾算法的查全率和精度，而且從圖6和圖7看來(lái)，它們無(wú)論對(duì)未分組過(guò)濾算法還是基于分組的傳播過(guò)濾算法的過(guò)濾器，性能的影響是很小的。

5 結(jié)束語(yǔ)

本文我們提出了基于內(nèi)容的元數(shù)據(jù)過(guò)濾算法?；诜纸M的傳播過(guò)濾算法可以有效處理訂閱達(dá)百萬(wàn)的工作負(fù)載。實(shí)驗(yàn)表明，當(dāng)訂閱量超過(guò)10000，基于分組的傳播過(guò)濾算法性能明顯超過(guò)未分組過(guò)濾算法。詞干提取和取消停用詞對(duì)算法的性能是很小的。但是這些技術(shù)的引進(jìn)對(duì)于提高系統(tǒng)的查全率和查準(zhǔn)率卻有很大的幫助。

在未來(lái)，我們計(jì)劃把算法擴(kuò)展到集群 （cluster of workstation）上，研究并行環(huán)境下系統(tǒng)性能的加速度。

［1］Yanlei Diao.Query processing for large—scale XML message brokering［D］.Doctor Dissertation，2005.

［2］The Dublin Core.The dublin core metadata initiative ［DB/OL］.［2012—12—02］.http：//dublincore.org.

［3］Francoise Fabret，Arno Jacobsen H，F(xiàn)ranqois Llirbat，et al.Filtering algorithms and implementation for very fast publish/subscribe systems［C］//Santa Barbara，California，USA：SIGMOD，2001.

［4］IBM，WebSphere MQ FAQ forum ［DB/OL］. ［2012—10—14］.http：//www.mqseries.net/.

［5］Markus Keidl.A publish and subscribe architecture for distributed metadata management ［C］//San Jose，CA：IEEE Computer Society ECDE，2006：309.

［6］Microsoft Corporation.Biz Talk server ［DB/OL］. ［2012—11—04］.http：//www.microsoft.com/biztalk.

［7］Wei Tai，OSullivan D，Keeney J.Distributed fault correlation scheme using a semantic publish/subscribe system ［C］//Salvador，Bahia，Brazil：Network Operations and Management Symposium，2008：835—838.

［8］Tova Milo，Tal Zur.Elad Verbin：Boosting topic—based publish—subscribe systems with dynamic clustering ［C］//Beijing，China：SIGMOD Conference，2007：749—760.

［9］Google.Google reader ［DB/OL］ .［2012—12—02］.http：//www.google.com/reader/view/.

［10］Wang Jinling，Jin Beihong，Li Jing.An ontology—based publish/subscribe system ［C］//Grenoble，F(xiàn)rance： Middleware，2005：232—253.

［11］W3C，Network news transfer protocol［DB/OL］.［2012—11—10］.http：//www.w3.org/Protocols/rfc977/rfc977.

［12］ MARC， MARC proposals ［DB/OL］ .［2012—12—03］.http：//www.loc.gov/marc/.