潘鄭冰,戴牡紅

(湖南大學(xué)軟件學(xué)院,長(zhǎng)沙410082)

實(shí)時(shí)數(shù)據(jù)倉(cāng)庫(kù)中一種改進(jìn)的數(shù)據(jù)流更新算法

潘鄭冰,戴牡紅

(湖南大學(xué)軟件學(xué)院,長(zhǎng)沙410082)

為實(shí)現(xiàn)數(shù)據(jù)倉(cāng)庫(kù)中數(shù)據(jù)的高效集成,針對(duì)數(shù)據(jù)偏斜分布現(xiàn)象,提出一種改進(jìn)的數(shù)據(jù)流更新算法EH-JOIN。該算法對(duì)傳統(tǒng)散列連接方法進(jìn)行改進(jìn),利用索引將部分頻繁使用的主數(shù)據(jù)存儲(chǔ)在內(nèi)存中,解決了高速數(shù)據(jù)流下的磁盤(pán)頻繁訪問(wèn)問(wèn)題。實(shí)驗(yàn)結(jié)果表明,與MESHJOIN算法和R-MESHJOIN算法相比,EH-JOIN算法的服務(wù)速率在磁盤(pán)存儲(chǔ)關(guān)系集保持適當(dāng)大小時(shí)分別提高了96%和81%,在內(nèi)存大小不同時(shí)提高了57%和48%。

實(shí)時(shí)數(shù)據(jù)倉(cāng)庫(kù);數(shù)據(jù)轉(zhuǎn)換;數(shù)據(jù)流更新;基于流的連接;哈希索引;偏斜分布

1 概述

為給企業(yè)提供及時(shí)有效的決策支持,實(shí)時(shí)數(shù)據(jù)倉(cāng)庫(kù)正在向數(shù)據(jù)新鮮度更高水平的方向發(fā)展,提供這些新的服務(wù)水平的工具和技術(shù)也正在迅速發(fā)展[1-2]。在實(shí)時(shí)數(shù)據(jù)倉(cāng)庫(kù)的環(huán)境下,數(shù)據(jù)更新中連接運(yùn)算的選擇主要取決于源數(shù)據(jù)的來(lái)源以及到達(dá)速率。源數(shù)據(jù)可能是突發(fā)性很強(qiáng)的大容量數(shù)據(jù)流,這會(huì)帶來(lái)極大的磁盤(pán)I/O開(kāi)銷(xiāo)。由于存儲(chǔ)在磁盤(pán)中查找表的訪問(wèn)速率相對(duì)緩慢,因此在連接操作中會(huì)出現(xiàn)瓶頸[3]。

為解決該問(wèn)題,文獻(xiàn)[4-5]提出一種MESHJOIN算法,特別針對(duì)一些如動(dòng)態(tài)數(shù)據(jù)倉(cāng)庫(kù)的連續(xù)數(shù)據(jù)流和存儲(chǔ)在磁盤(pán)中關(guān)系集的連接,但該算法對(duì)于連接組件之間的內(nèi)存分配不夠理想,而且訪問(wèn)磁盤(pán)存儲(chǔ)關(guān)系采取的策略不夠高效。文獻(xiàn)[6]利用一種改進(jìn)的算法解決了連接部件中內(nèi)存的最佳分配問(wèn)題。文獻(xiàn)[7]提出基于分塊的連接算法來(lái)改善MESHJOIN的性能,可以處理間歇的數(shù)據(jù)流。除此之外,還有一些研究更關(guān)注于實(shí)時(shí)數(shù)據(jù)流的連接響應(yīng)效率問(wèn)題,如PMJ算法[8]和RPJ算法[9],都支持在不用完全排序的基礎(chǔ)上盡可能快地產(chǎn)生一小部分連接結(jié)果,以達(dá)到快速響應(yīng)的效果。文獻(xiàn)[10]采用多線程并發(fā)連接技術(shù),合理調(diào)度了實(shí)時(shí)元組和準(zhǔn)實(shí)時(shí)元組的執(zhí)行。文獻(xiàn)[11]提出一種支持服務(wù)質(zhì)量的更新和查詢的調(diào)度算法,實(shí)現(xiàn)了更新和查詢的實(shí)時(shí)調(diào)度。

雖然MESHJOIN算法能有效地分?jǐn)偪焖俚妮斎肓鲙?lái)的磁盤(pán)I/O開(kāi)銷(xiāo),但它不能適應(yīng)實(shí)際應(yīng)用中的一般特征,比如在許多市場(chǎng)上少數(shù)產(chǎn)品具有較高的購(gòu)買(mǎi)頻率[12]。本文針對(duì)實(shí)際中常見(jiàn)的數(shù)據(jù)偏斜分布情況,提出一種改進(jìn)的數(shù)據(jù)流更新算法:擴(kuò)展混合連接算法(EH-JOIN)。EH-JOIN的關(guān)鍵特征是將存儲(chǔ)在磁盤(pán)的關(guān)系集使用最多的部分存在內(nèi)存中,使其與數(shù)據(jù)流中的頻繁項(xiàng)相匹配。

2 基于數(shù)據(jù)流的連接

數(shù)據(jù)連接作為實(shí)時(shí)數(shù)據(jù)倉(cāng)庫(kù)的ETL(Extraction, Transformation,Loading)過(guò)程中常見(jiàn)的數(shù)據(jù)轉(zhuǎn)換操作,通常表示為SR,其中,S表示特定的數(shù)據(jù)源;表示特定的連接操作;R表示數(shù)據(jù)倉(cāng)庫(kù)中的關(guān)系集合。如圖1所示,對(duì)于實(shí)時(shí)數(shù)據(jù)流中的數(shù)據(jù)更新來(lái)說(shuō),S包含內(nèi)容與到達(dá)速率都在不斷變換的數(shù)據(jù)元組,到達(dá)的每一個(gè)元組都要和R完成連接操作。R是一個(gè)包含了大量主數(shù)據(jù)的關(guān)系集合,通常存儲(chǔ)在磁盤(pán)中。在實(shí)際連接操作中,由于內(nèi)存大小的限制,R不能全部導(dǎo)入到內(nèi)存中,因此必須將R中的元組不停地讀入有限的內(nèi)存中,這就帶來(lái)了巨大的I/O開(kāi)銷(xiāo)。當(dāng)磁盤(pán)I/O速率比數(shù)據(jù)元組的到達(dá)速率慢時(shí),就會(huì)造成連接操作的瓶頸,影響ETL的實(shí)時(shí)性。在MESHJOIN算法中,盡管R中的數(shù)據(jù)元組是分批讀入到內(nèi)存中的,這有助于分?jǐn)侷/O開(kāi)銷(xiāo),但對(duì)于每一批數(shù)據(jù)流元組,R都需完整地讀入到內(nèi)存中。而實(shí)際情況并不是R中所有元組都要和數(shù)據(jù)流中的數(shù)據(jù)元組做連接操作,這就導(dǎo)致很多無(wú)效元組被讀入內(nèi)存中,帶來(lái)了很多無(wú)效的磁盤(pán)I/O。

圖1 基于數(shù)據(jù)流連接的實(shí)例

3 一種改進(jìn)的數(shù)據(jù)流更新算法EH-JOIN

3.1 基于索引的哈希連接結(jié)構(gòu)

相比MESHJOIN,EH-JOIN有2個(gè)關(guān)鍵的改進(jìn): (1)修改了Hash連接組件讓它可以利用索引。(2)將頻繁使用的主數(shù)據(jù)緩存到內(nèi)存中,極大地減少了I/O消耗。

EH-JOIN將基于磁盤(pán)存儲(chǔ)的關(guān)系集R和數(shù)據(jù)流S相連接。假設(shè)R的連接屬性有一個(gè)非聚集索引,并且這個(gè)連接屬性對(duì)于主數(shù)據(jù)來(lái)說(shuō)是唯一的。這種假設(shè)是很自然的,并且符合常見(jiàn)的應(yīng)用領(lǐng)域,比如在密鑰交換中。

EH-JOIN算法的體系結(jié)構(gòu)如圖2所示。該算法主要消耗內(nèi)存的部分為磁盤(pán)緩存、哈希表、隊(duì)列和數(shù)據(jù)流緩存,而存儲(chǔ)在磁盤(pán)中的關(guān)系集R和數(shù)據(jù)流S作為輸入流。假設(shè)R擁有連接屬性的索引作為鍵。該算法將數(shù)據(jù)流元組存在哈希表中,該哈希表占用的算法內(nèi)存最多。此外,本文算法還為數(shù)據(jù)元組提供了標(biāo)識(shí)符,并將這些標(biāo)示符存入隊(duì)列中,tm隊(duì)列需要支持隨機(jī)刪除,最簡(jiǎn)單的實(shí)現(xiàn)方法是雙向鏈表。

圖2 EH-JOIN算法的體系結(jié)構(gòu)

EH-JOIN是一種迭代算法,在每次迭代中,磁盤(pán)關(guān)系集R的一個(gè)分塊作為一個(gè)探測(cè)輸入。因此,這個(gè)分塊被裝載到磁盤(pán)緩存中且僅占用磁盤(pán)緩存的一部分。之后,本文算法執(zhí)行了一個(gè)典型的哈希連接操作,即它遍歷磁盤(pán)緩沖區(qū)的所有元組,并在哈希表中進(jìn)行查找。每一次匹配成功,算法就會(huì)輸出那個(gè)匹配的數(shù)據(jù)流元組。

同樣地,在每次迭代中,EH-JOIN都會(huì)彈出匹配的元組。假設(shè)聯(lián)接屬性是R中唯一證明這個(gè)操作正確性的屬性。彈出一個(gè)元組意味著同時(shí)從哈希表和隊(duì)列中刪除這個(gè)元組。本文算法還保留一個(gè)計(jì)數(shù)器ω來(lái)計(jì)算彈出元組的數(shù)目。在處理完整個(gè)磁盤(pán)緩存后,算法從數(shù)據(jù)流緩沖中讀取ω個(gè)新元組,將它們裝入哈希表中同時(shí)在隊(duì)列中插入標(biāo)識(shí)符。

為選擇R中的下一個(gè)分塊,EH-JOIN考慮隊(duì)列中最舊的數(shù)據(jù)流元組的連接屬性。利用索引,把R中具有該連接屬性值的分塊加載到磁盤(pán)緩存中,這樣每個(gè)加載分塊都至少可以和一個(gè)數(shù)據(jù)流元組匹配,進(jìn)一步保持它的自適應(yīng)性。

與MESHJOIN一樣,EH-JOIN能在任何數(shù)據(jù)分布情況下工作。然而,在實(shí)踐中,某些特定分布十分常見(jiàn)。目前研究表明,銷(xiāo)售數(shù)據(jù)通常服從冪次法則,或者Zipfian分布[11]。符合冪次法則分布的主要區(qū)別在于它們的指數(shù)。指數(shù)等于1時(shí),得到的分布滿足Zipf定律,也就是通常所說(shuō)的Zipfian分布。在商業(yè)中,80/20規(guī)則被用于模擬場(chǎng)景,當(dāng)少量商品的出售頻率遠(yuǎn)高于其他產(chǎn)品時(shí),往往簡(jiǎn)化成80/20規(guī)則[11],該規(guī)則在商業(yè)應(yīng)用中非常普遍。80/20規(guī)則對(duì)應(yīng)于一個(gè)指數(shù)略小于1的冪次分布情況。

3.2 EH-JOIN算法

EH-JOIN算法具體如下:

輸入 磁盤(pán)存儲(chǔ)帶有索引的關(guān)系集R以及更新數(shù)據(jù)流S

輸出 S與R的連接

參數(shù) S中ω個(gè)元組以及R中的一個(gè)分塊pi

一旦將內(nèi)存分配給連接組件,就開(kāi)始按照上述步驟執(zhí)行算法。在開(kāi)始實(shí)際連接操作前,本文算法先將磁盤(pán)存儲(chǔ)的關(guān)系集R中的一部分讀進(jìn)磁盤(pán)緩存的非交換區(qū)(第1行)。一開(kāi)始,哈希表H是空的;因此,將hS賦給ω(第2行)。本文算法包含2層循環(huán)。一個(gè)是外層循環(huán),這是一個(gè)無(wú)限循環(huán)(第3行)。外層循環(huán)的主要目的是把數(shù)據(jù)流壓入到哈希表中。在外層循環(huán)中,還有2個(gè)獨(dú)立的內(nèi)層循環(huán)。一個(gè)是實(shí)現(xiàn)磁盤(pán)緩存非交換區(qū)的探測(cè)功能,另一個(gè)是實(shí)現(xiàn)磁盤(pán)緩存交換區(qū)的探測(cè)功能。外層循環(huán)一啟動(dòng),算法就開(kāi)始觀測(cè)數(shù)據(jù)流緩存的狀態(tài)。如果數(shù)據(jù)流可以讀取,算法就從數(shù)據(jù)流緩存中讀取ω個(gè)元組存入哈希表中,并將它們的屬性值存入隊(duì)列中。讀完后算法將ω重設(shè)為0(第4行～第7行),然后開(kāi)始執(zhí)行第一個(gè)內(nèi)層循環(huán),遍歷磁盤(pán)緩存的非交換區(qū)中的所有元組并在哈希表中查找它們。一旦有元組匹配,就產(chǎn)生一個(gè)連接輸出。由于采用多重哈希映射表,因此一個(gè)磁盤(pán)元組可能有多個(gè)數(shù)據(jù)元組匹配。產(chǎn)生連接輸出后,就從哈希表中刪除所有匹配過(guò)的元組,并且從隊(duì)列中刪除它們對(duì)應(yīng)的節(jié)點(diǎn)。哈希表中每刪除一個(gè)元組,計(jì)數(shù)器ω就加1(第8行～第13行)。在開(kāi)始第二個(gè)內(nèi)層循環(huán)之前,算法讀取隊(duì)列中最舊的連接屬性值,利用這個(gè)連接屬性值作為索引將磁盤(pán)分塊pi(2≤i≤n)讀到磁盤(pán)緩存的交換區(qū)中(第14行～第15行)。當(dāng)特定的磁盤(pán)分塊被讀入到磁盤(pán)緩存的交換區(qū)后,算法開(kāi)始執(zhí)行第二個(gè)內(nèi)層循環(huán),然后開(kāi)始重復(fù)上述第一個(gè)內(nèi)層循環(huán)的所有步驟(第16行～第21行)。

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

本文通過(guò)實(shí)驗(yàn)比較EH-JOIN算法和MESHJOIN算法,使用已知傾斜分布的合成數(shù)據(jù)集來(lái)做測(cè)試。

4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)設(shè)置具體如下:

(1)硬件說(shuō)明:實(shí)驗(yàn)采用酷睿2處理器,2.13 GHz主頻,4 GB內(nèi)存,操作系統(tǒng)是Window XP,分配給測(cè)試程序的最大內(nèi)存為250 MB。算法用Java實(shí)現(xiàn),實(shí)驗(yàn)使用Apache內(nèi)置插件和Java API,測(cè)量?jī)?nèi)存消耗和處理時(shí)間。

(2)數(shù)據(jù)說(shuō)明:實(shí)驗(yàn)用指數(shù)為1的Zipf’s法則生成的數(shù)據(jù)來(lái)測(cè)試算法。所生成的數(shù)據(jù)流具有突發(fā)性和自相似性。本文使用MYSQL5.0數(shù)據(jù)庫(kù)將關(guān)系集R存儲(chǔ)在磁盤(pán)中,其中,關(guān)系集R大小為50萬(wàn)～800萬(wàn)個(gè)元組不等,每個(gè)元組為120 Byte,流數(shù)據(jù)中一個(gè)元組為20 Byte,隊(duì)列的一個(gè)節(jié)點(diǎn)為12 Byte。為準(zhǔn)確測(cè)量每一次I/O操作中的開(kāi)銷(xiāo),將提取結(jié)果集合的大小和磁盤(pán)上一個(gè)分區(qū)的大小設(shè)置為相同。EH-JOIN算法需要在哈希表中一個(gè)鍵對(duì)應(yīng)多個(gè)值,實(shí)驗(yàn)通過(guò)Apache提供的多重哈希映射表來(lái)實(shí)現(xiàn)。

(3)評(píng)價(jià)策略:定義服務(wù)速率作為算法的性能判斷標(biāo)準(zhǔn),服務(wù)速率越高,算法性能越好。服務(wù)速率是每秒中被處理的數(shù)據(jù)元組的個(gè)數(shù)。每次實(shí)驗(yàn)算法執(zhí)行1 h。實(shí)驗(yàn)開(kāi)始20 min后開(kāi)始測(cè)量,連續(xù)測(cè)量20 min。為增加準(zhǔn)確性,本文實(shí)驗(yàn)對(duì)每種規(guī)格采集3種數(shù)據(jù),然后計(jì)算出平均值。

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

將EH-JOIN算法與MESHJOIN算法、R-MESHJOIN算法進(jìn)行實(shí)驗(yàn),比較結(jié)果如下:

(1)性能比較:能夠直接影響算法性能的2個(gè)參數(shù)是可用內(nèi)存總量以及磁盤(pán)存儲(chǔ)的關(guān)系集大小。在實(shí)驗(yàn)中,測(cè)試不同參數(shù)對(duì)算法的影響,并比較它們的性能。

(2)不同大小磁盤(pán)存儲(chǔ)關(guān)系集下的性能比較,如圖3所示,假設(shè)分配給連接的內(nèi)存大小是固定的,同時(shí)磁盤(pán)存儲(chǔ)的關(guān)系集大小呈指數(shù)級(jí)增長(zhǎng)。如圖3(a)所示,對(duì)于所有不同大小的關(guān)系集R,EH-JOIN的性能總體優(yōu)于所有其他算法。在R保持適當(dāng)大小時(shí), EH-JOIN算法的服務(wù)速率比MESHJOIN算法提高了96%,比R-MESHJOIN算法提高了81%,即使由于R逐漸增到導(dǎo)致算法性能降低時(shí),EH-JOIN相對(duì)于其他算法性能仍具有一定優(yōu)勢(shì)。

(3)可用內(nèi)存大小不同時(shí)的性能比較:在第(2)組實(shí)驗(yàn)中,關(guān)系集R的大小固定為2×107個(gè)元組,分析EH-JOIN使用不同大小內(nèi)存時(shí)的性能。實(shí)驗(yàn)結(jié)果如圖3(b)所示。

圖3 算法性能比較

實(shí)驗(yàn)數(shù)據(jù)表明,對(duì)于不同的內(nèi)存大小,EH-JOIN的性能明顯優(yōu)于其他算法。在相同條件下,EHJOIN算法的服務(wù)速率比MESHJOIN算法提高了57%,比R-MESHJOIN算法提高了48%?？梢?jiàn),EHJOIN在磁盤(pán)緩存中保持一個(gè)交換區(qū)和一個(gè)非交換區(qū)對(duì)性能提升有較大作用。

非交換部分在數(shù)據(jù)流處理中的作用:為更好地了解磁盤(pán)緩存中非交換部分的作用,統(tǒng)計(jì)僅用磁盤(pán)緩存中的非交換部分處理的數(shù)據(jù)流元組,實(shí)驗(yàn)結(jié)果如圖4所示,設(shè)置非交換部分的大小和交換部分的大小一樣。

圖4 4 000次迭代中非交換區(qū)處理的數(shù)據(jù)元組總量

從圖4可以看出,在4 000次迭代中,當(dāng)內(nèi)存大小為50 MB,關(guān)系集R的大小為2×107個(gè)元組時(shí),大約4×104個(gè)數(shù)據(jù)流元組要通過(guò)磁盤(pán)緩存中的非交換部分處理,而且如果實(shí)驗(yàn)增大整體分配的內(nèi)存,那么這個(gè)數(shù)量還會(huì)增加。對(duì)于250 MB內(nèi)存和同樣大小的關(guān)系集R,這個(gè)數(shù)量會(huì)達(dá)到2×107以上。在其他算法中,由于這種非交換的部分每次從磁盤(pán)中載入,因此I/O成本會(huì)明顯增加。

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

偏斜分布的數(shù)據(jù)集在實(shí)際應(yīng)用場(chǎng)景中十分常見(jiàn),而經(jīng)典的MESHJOIN算法在這種數(shù)據(jù)集上進(jìn)行連接操作的性能很差,因此,本文提出一種改進(jìn)的數(shù)據(jù)流更新算法EH-JOIN,該算法使用磁盤(pán)存儲(chǔ)的主數(shù)據(jù)的索引結(jié)構(gòu)來(lái)迅速存取磁盤(pán)分塊,并且緩存了主數(shù)據(jù)中使用最頻繁的元組匹配數(shù)據(jù)流中的頻繁項(xiàng),大大減少了磁盤(pán)的訪問(wèn)量。實(shí)驗(yàn)結(jié)果表明,在不同磁盤(pán)關(guān)系集或者不同內(nèi)存大小下,該算法都能在性能上得到較好的提升。在今后工作將進(jìn)一步提高算法的內(nèi)存使用效率。

[1] Karakasidis A,Vassiliadis P,Pitoura E.ETL Queues for Active Data Warehousing[C]//Proc.ofthe 2nd InternationalWorkshop on Information Quality in Information Systems.New York,USA:ACM Press, 2005:28-39.

[2] 林子雨,楊冬青,宋國(guó)杰,等.實(shí)時(shí)主動(dòng)數(shù)據(jù)倉(cāng)庫(kù)中的變化數(shù)據(jù)捕捉研究綜述[J].計(jì)算機(jī)研究與發(fā)展, 2007,44(z3):447-451.

[3] Golab L,Johnson T,SeidelJ S,etal.Stream Warehousing with Data Depot[C]//Proc.of the 35th SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2009:847-854.

[4] Polyzotis N,Skiadopoulos S,Vassiliadis P,etal. Supporting Streaming Updatesin an Active Data Warehouse[C]//Proc.of the 23rd International Conference on Data Engineering.New Jersey,USA: IEEE Computer Society,2007:476-485.

[5] Polyzotis N,Skiadopoulos S,Vassiliadis P,etal. Meshing Streaming Updates with Persistent Data in an Active Data Warehouse[J].IEEE Transactions on Knowledge and DataEngineering,2008,20(7): 976-991.

[6] Naeem M,Dobbie G,Weber G.R-MESHJOIN for Nearreal-time Data Warehousing[C]//Proc.of the 13th InternationalWorkshop on Data Warehousing and OLAP.New York,USA:ACM Press,2010:53-60.

[7] Chakraborty A,Singh A.A Partition-based Approach to Support Streaming Up-dates over Persistent Data in an Active Data Warehouse[C]//Proc.of 2009IEEE InternationalSymposium on Parallel& Distributed Processing.Washington D.C.,USA:IEEE Computer Society,2009:1-11.

[8] Chandrasekaran S,Franklin M J.PSoup:A System for Streaming Queries over Streaming Data[J].The VLDB Journal,2003,12(2):140-156.

[9] Tao Yufei,Yiu M,Papadias D.Producing Fast Join Results on Streams Through Rate-based Optimization [C]//Proc.of ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press, 2005:371-382.

[10] 林子雨,林 琛,馮少榮,等.MESHJOIN*:實(shí)時(shí)數(shù)據(jù)倉(cāng)庫(kù)環(huán)境下的數(shù)據(jù)流更新算法[J].計(jì)算機(jī)科學(xué)與探索,2010,4(10):927-939.

[11] 師金鋼,鮑玉斌,冷芳玲,等.實(shí)時(shí)數(shù)據(jù)倉(cāng)庫(kù)中支持QoS的更新和查詢?nèi)蝿?wù)調(diào)度[J].小型微型計(jì)算機(jī)系統(tǒng),2011,32(5):801-806.

[12] Erik B,Hu Yu,Duncan S.Goodbye Pareto Principle, Hello Long Tail:The Effect of Search Costs on the Concentration ofProductSales[J].Management Science,2011,57(8):1373-1386.

編輯 陸燕菲

An Improved Data Stream Update Algorithm in Real-time Data Warehouse

PAN Zheng-bing,DAI Mu-hong
(College of Software,Hunan University,Changsha 410082,China)

To achieve data efficient integration in data warehouse,aiming at the phenomenon of data skew distribution,this paper proposes an improved data stream update algorithm——Extended Hybrid Join(EH-JOIN).The algorithm improves the traditional Hash join method,and it can adapt to common skewed data and greatly reduce the disk I/O cost through using index structure and storing some parts of the master data in memory.Experimental results show that the service rate of proposed algorithm is improved by 96%and 80%compared with MESHJOIN algorithm and R-MESHJOUIN algorithm as the relation set keeps an appropriate size,and the service rate of proposed algorithm is improved by 57%and 48%compared with MESHJOIN algorithm and R-MESHJOUIN algorithm as the memory size differs.

real-time data warehouse;data transformation;data stream update;stream-based join;Hash index; skewed distribution

1000-3428(2014)10-0043-04

A

TP311.13

10.3969/j.issn.1000-3428.2014.10.009

湖南省自然科學(xué)基金資助項(xiàng)目(2011FJ3034)。

潘鄭冰(1988-),女,碩士研究生,主研方向:數(shù)據(jù)庫(kù)技術(shù),決策支持,知識(shí)工程;戴牡紅,副教授。

2013-08-13

2013-10-12E-mail:panzhengbing@163.com

中文引用格式:潘鄭冰,戴牡紅.實(shí)時(shí)數(shù)據(jù)倉(cāng)庫(kù)中一種改進(jìn)的數(shù)據(jù)流更新算法[J].計(jì)算機(jī)工程,2014,40(10):43-46,51.

英文引用格式:Pan Zhengbing,Dai Muhong.An Improved Data Stream Updating Algorithm in Real-time Data Warehouse[J].Computer Engineering,2014,40(10):43-46,51.