kFilter-基于關(guān)鍵字查詢的XML流過濾系統(tǒng).pdf

1、隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展和XML逐漸成為數(shù)據(jù)存儲(chǔ)和交換的標(biāo)準(zhǔn)，出現(xiàn)了很多與XML數(shù)據(jù)流緊密相關(guān)的應(yīng)用，例如，SDI(Selective Dissemination ofInformation)。針對(duì)這些問題，人們提出很多解決方案，比較有代表性的是基于自動(dòng)機(jī)的過濾方法和基于索引的過濾方法。
　　 當(dāng)前幾乎所有的XML數(shù)據(jù)流處理方面的研究都是基于XPath或XQuery的，這主要會(huì)帶來兩個(gè)問題：首先，用戶必須熟悉一門復(fù)雜的查詢語言，

2、而這一點(diǎn)對(duì)很多用戶，尤其是初級(jí)用戶是很不切實(shí)際的；其次，用戶還必須知道流過來的數(shù)據(jù)的結(jié)構(gòu)(或模式，schema)，這樣他們才能夠?qū)懗霾樵儊怼?br>　　 針對(duì)存在的問題，文章[20]首先提出了在XML數(shù)據(jù)流上使用關(guān)鍵字查詢的方式。關(guān)鍵字查詢是一種對(duì)用戶有好的查詢方式，并且被廣泛地應(yīng)用于信息檢索等領(lǐng)域。它的最大優(yōu)點(diǎn)在于其簡單性。對(duì)XML流數(shù)據(jù)用關(guān)鍵字來進(jìn)行查詢，用戶就不必掌握一種查詢語言，也不需要知道流數(shù)據(jù)的模式。盡管[20]中提出了一

3、種基于棧的Lookup算法來對(duì)XML數(shù)據(jù)流進(jìn)行關(guān)鍵字查詢，但是其算法并不是高效的，并且該算法只是針對(duì)單個(gè)查詢而言的，文章中并沒有提出如何對(duì)多個(gè)查詢進(jìn)行過濾的方法，這與現(xiàn)實(shí)中流處理系統(tǒng)往往擁有大量的用戶查詢不符合。
　　 本文提出了最右包含邊界的概念，并在此基礎(chǔ)上提出了處理單個(gè)查詢的算法XVirtualStack(XVS)，它使用一個(gè)虛擬的棧并配合一個(gè)位置向量來“緩存”流中遇到的所有關(guān)鍵字。在XVS的基礎(chǔ)上，我們給出了kFilte