鄭曉艷，孫濟洲

(1. 天津大學(xué)計算機科學(xué)與技術(shù)學(xué)院，天津 300072；2. 天津職業(yè)技術(shù)師范大學(xué)信息技術(shù)工程學(xué)院，天津 300222)

頻繁模式挖掘在數(shù)據(jù)挖掘中起著非常重要的作用，目前已經(jīng)提出的頻繁模式挖掘算法大致可歸結(jié)為2類．第 1類是產(chǎn)生候選集的算法，這類算法主要應(yīng)用 Apriori性質(zhì)[1]，遞歸地從 k頻繁模式中產(chǎn)生 k+1候選模式，通過掃描數(shù)據(jù)庫確定一個候選模式是否是頻繁的．第 2類是基于 FP-tree[2]的方法，該方法建立一棵前綴樹，稱為 FP-tree，只對數(shù)據(jù)庫掃描一遍，將數(shù)據(jù)庫所包含的模式信息保存在這棵樹上，從 FP-tree上挖掘頻繁模式．在以上方法的基礎(chǔ)上發(fā)展了相當多的并行算法，影響較大的有 CD(count distribution)算法、DD(data distribution)算法[3]，PDM (parallel data mining)算法[4]．CD算法在各處理器上水平劃分數(shù)據(jù)庫，采用冗余計算避免處理器之間的通信，所以該算法的通信量小，但是不能充分利用整個系統(tǒng)的內(nèi)存．DD算法在處理器之間劃分頻繁項集，解決了計算規(guī)?？梢噪S節(jié)點個數(shù)增加而增加的問題，但是處理器之間的廣播帶來了很大的通信負載，在節(jié)點增加時也增加了通信的開銷．CD算法和DD算法都存在對每個候選集需要掃描整個數(shù)據(jù)庫的問題，以及每次掃描結(jié)束時各個處理器需要同步的問題．PDM 算法和CD算法類似，用Hash表維護局部候選k項集．為了構(gòu)成全局候選項集，采用一種稱為 clue-and-poll的技術(shù)，只選取少量可能滿足支持度要求的表項在處理器之間交換，并且實現(xiàn)了Hash表的并行生成，算法在候選集增大的時候有較好的可擴展性．

MLFPT(multiple local frequent pattern tree)算法[5]是在共享存儲結(jié)構(gòu)上提出的基于 FP-tree的頻繁項集挖掘算法．均勻劃分數(shù)據(jù)庫，每個處理器生成一個局部頻繁模式樹，并在所有處理器之間共享．只對數(shù)據(jù)庫掃描 2次，而且不會產(chǎn)生大量頻繁項集，對長規(guī)則的適應(yīng)性很強．但是當處理稀疏數(shù)據(jù)時，由于FP-tree上的可共享節(jié)點減少，造成樹結(jié)構(gòu)過大，效率甚至低于Apriori類算法．

實際上，很多應(yīng)用數(shù)據(jù)庫呈現(xiàn)稀疏狀態(tài)，如超市的銷售數(shù)據(jù)庫．有少部分文獻論述了當數(shù)據(jù)源為勻質(zhì)或非勻質(zhì)時算法的運行效率問題以及解決方法．但專門針對某種特殊數(shù)據(jù)源進行的研究還不多見．陳惠萍等[6]針對稀疏數(shù)據(jù)源提出了 FP-tree和支持度數(shù)組相結(jié)合的方法挖掘最大頻繁項集，用二維數(shù)組保存所有可能的頻繁2項集的支持度，用于查找某個項目的條件模式庫中的所有頻繁項．文獻[7]中也用到了類似的二維矩陣．該方法減少了遍歷 FP-tree的次數(shù)，但是也引入了一定的時間和空間開銷．而且仍然采用 FP-tree存儲數(shù)據(jù)庫信息，如果對其并行化，建立FP-tree仍然是算法的瓶頸．

另外，由于消息傳遞模型和共享存儲模型在計算性能上的明顯差異，大部分算法都是在消息傳遞計算模型上提出的．實際上，共享存儲計算模型在程序設(shè)計時由于不需考慮消息傳遞的時間、對象和內(nèi)容，編程方面具有非常大的優(yōu)勢，但在傳統(tǒng)的共享存儲模型上，這些程序設(shè)計方面的優(yōu)勢也正是計算性能差的主要原因．為了提高共享存儲計算環(huán)境的性能，Huang等[8]提出了一種面向視圖的并行編程(view oriented parallel programming，VOPP)思想，用視圖作為一致性維護的基本單元．程序員可以根據(jù)算法特點把數(shù)據(jù)對象劃分成多個視圖．VODCA (view-oriented，distributed，cluster-based approach)[9]是基于 VOPP 實現(xiàn)的面向視圖的分布式集群計算方法，實現(xiàn)了一致性維護中的時間選擇、處理器選擇和數(shù)據(jù)選擇，借鑒了Trademarks的內(nèi)存維護策略并進行改進，解決了Trademarks中 diffs積累問題．使得其計算性能較傳統(tǒng)的共享存儲計算環(huán)境有了很大的提高[10]．

本文針對稀疏數(shù)據(jù)源，設(shè)計了一種鏈表結(jié)構(gòu)，提出了稀疏數(shù)據(jù)源頻繁項集挖掘并行算法(parallel mining frequent itemsets from sparse data source，PMFSD)，并在VODCA上實現(xiàn)．

1 FI-list設(shè)計和構(gòu)造

為了提高頻繁項集的計算速度，F(xiàn)I-list的設(shè)計和構(gòu)造主要從3個方面加以考慮：①減少數(shù)據(jù)庫掃描次數(shù)以降低 I/O數(shù)量；②及時有效地對數(shù)據(jù)進行剪枝以減少候選集的數(shù)量；③避免保存大量候選項集以降低內(nèi)存占用量．

1.1 FI-list的設(shè)計

鏈表結(jié)構(gòu)體 FI-list的設(shè)計借鑒了稀疏矩陣的列壓縮存儲策略．稀疏矩陣的基本列壓縮存儲格式是使用 3個數(shù)組 AA、JA和 IA，數(shù)組 AA存儲按 1～n列排列的非零矩陣元素，整型數(shù)組JA表示AA中對應(yīng)元素所在的行號，整型數(shù)組 IA中的元素是每一列的開始在 JA中的索引號．把源數(shù)據(jù)庫看作一個稀疏矩陣，每個事務(wù)表示一個行向量，每個項目代表一個列向量．如果頻繁模式挖掘中使用的輸入數(shù)據(jù)是二元的，即只要求明確項目是否是非零的，數(shù)據(jù)源就可以被看作一個二元稀疏矩陣，如圖1所示．

圖1 示例數(shù)據(jù)源Fig.1 Instance of data source

該矩陣采用標準列壓縮格式可以存儲為

因為矩陣是二元的，非零數(shù)據(jù)即是 1，無須專門記錄，所以數(shù)組 AA可以省略．本文在此基礎(chǔ)上對以上表示方法加以改造，只保留數(shù)組JA．在其中增加每個列的開始標記，這里用數(shù)字0來表示．

算法實現(xiàn)中可以對以上存儲結(jié)果進一步壓縮，根據(jù)設(shè)定的最小支持數(shù)，從中去除支持數(shù)小于最小支持數(shù)的項集所對應(yīng)的列信息，例如，最小支持數(shù)為2時，上述矩陣最終變換為

經(jīng)過對數(shù)據(jù)庫的二元映射和存儲變換之后，對頻繁項集的計數(shù)掃描就可以在一維鏈表上進行了．

如圖 2所示，鏈表結(jié)構(gòu)體由 2部分構(gòu)成：項目頭表(HB)和事務(wù)鏈表(TL)．其中HB用于存放產(chǎn)生的頻繁項集和相應(yīng)的支持度、地址信息，每一個表項有3個域，內(nèi)容(Contents)域保存項集內(nèi)容，支持度(Sup)域保存各項集的支持度，地址(Add)域存放與該項集相關(guān)的事務(wù)鏈表頭．TL是一個線性鏈表，存放與項集相關(guān)的事務(wù)號(TID)序列．事務(wù)號序列T(ISi)＝Ti,k1，Ti,k2, … ,Ti,ksi(i = 1,2,… ,n )，其中 k1＜ k2＜ …＜ksi．

圖2 頻集鏈表結(jié)構(gòu)體Fig.2 Unit of frequent itemsets list

數(shù)據(jù)集越稀疏，與每個項目相關(guān)的事務(wù)數(shù)目越少，相關(guān)的交易鏈長度越?。ǔＴ陬l繁 2-項集之后，隨著頻繁項集長度增加，相關(guān)的事務(wù)數(shù)目急劇減少，整個鏈表尺寸很小，容易裝入內(nèi)存．但在非稀疏數(shù)據(jù)集情況下，由于鏈結(jié)構(gòu)的開銷，整個鏈表實際尺寸會大于相應(yīng)的二元數(shù)據(jù)庫，需要更多的存儲空間．

FI-list結(jié)構(gòu)也可以在其他共享內(nèi)存編程環(huán)境和消息傳遞平臺上使用，作為稀疏數(shù)據(jù)源頻繁項集挖掘的數(shù)據(jù)結(jié)構(gòu)．在消息傳遞平臺上，整個 k-項集相關(guān)信息和鏈表可以在處理器之間進行復(fù)制，作為計算k+1項集的依據(jù)．另外需要一個事務(wù)長度表 LB，記錄每個事務(wù)的長度，用于產(chǎn)生候選集時的剪枝條件．

1.2 FI-list的構(gòu)造

構(gòu)造FI-list有如下4個步驟．

(1)對數(shù)據(jù)庫按行掃描一次，統(tǒng)計各個事務(wù)的長度，生成LB．

(2)對數(shù)據(jù)庫按列掃描一次，按設(shè)定的最小支持度，生成頻繁 1-項集；每生成一個頻繁 1-項集，按第1.1節(jié)中TM所示的順序向事務(wù)細節(jié)表TL寫入與該項目相關(guān)的事務(wù)號序列，同時向頭表HB中寫入該列對應(yīng)的項目內(nèi)容和支持度，并且使地址域指向TL．

(3)按照 Apriori性質(zhì)，從(k-1)-項集生成 k-項集，同時根據(jù) LB表進行剪枝．此過程由函數(shù) Gen()遞歸實現(xiàn)．

(4)直到不能生成更高維頻繁項集，F(xiàn)I-list構(gòu)造結(jié)束．此時FI-list中保存了所有頻繁項集及其支持度．

Gen函數(shù)所包含的算法如下：

2 VODCA環(huán)境下PMFSD算法實現(xiàn)

2.1 VODCA編程環(huán)境的特點

VODCA程序編譯使用標準C或者C++編譯器，程序中只須包含其提供的頭文件，即可調(diào)用并行計算所需的相關(guān)系統(tǒng)常數(shù)和視圖操作原語．程序員的主要工作是根據(jù)算法和數(shù)據(jù)結(jié)構(gòu)的特征，把共享數(shù)據(jù)劃分成視圖，并且在程序中正確使用視圖．對視圖的劃分和使用要考慮4個特點：①視圖的內(nèi)容可以根據(jù)算法和數(shù)據(jù)的特點任意劃分；②視圖一旦確定，在整個程序中不能改變；③每次只能對一個視圖進行排他訪問，但是允許對一個或多個視圖嵌套使用只讀訪問；④無論算法中對共享數(shù)據(jù)的訪問是否存在爭用，任何對共享數(shù)據(jù)的操作(包括只讀訪問和讀寫訪問)都必須調(diào)用視圖訪問原語(只讀訪問原語或者排他訪問原語)．

2.2 問題中的視圖定義

由于共享內(nèi)存結(jié)構(gòu)上編程的方便性，算法實現(xiàn)不必考慮數(shù)據(jù)的分布．根據(jù) VOPP的特點，劃分視圖成為了算法實現(xiàn)的焦點問題．算法中涉及到的共享數(shù)據(jù)包括：數(shù)據(jù)源 DB、事務(wù)長度表 LB和 FI-list．其中對DB的共享訪問是只讀的，整個DB可以定義為一個視圖．生成 LB時需要進行寫訪問，可以按任務(wù)劃分定義視圖，例如有 n個處理器，則對事務(wù)長度的統(tǒng)計就劃分成n個任務(wù)，每個任務(wù)相關(guān)的LB部分定義為一個視圖．FI-list要保存所有的頻繁項集，每次產(chǎn)生一個新的頻繁項集，都會發(fā)生對它的寫操作，所以對FI-list相關(guān)視圖的劃分是程序設(shè)計的重點．

視圖劃分結(jié)果如圖 3表示．對項目頭表 HB，每個 k-項集(k＝1，2，…，m)的全體劃分為一個視圖，而對事務(wù)鏈表 TL，每個鏈劃分為一個視圖．這些視圖都是在算法運行過程中動態(tài)產(chǎn)生的，每個視圖可以通過編程獲得唯一的編號．這樣劃分視圖主要依據(jù)以下3個方面．

(1) 每個 k-項集的相關(guān)信息只在生成 k-項集時要求讀寫訪問，在使用 k-項集生成(k+1)-項集時，k-項集的相關(guān)信息是只讀共享的．所以只需考慮在生成k-項集時對數(shù)據(jù)對象訪問的特點．

(2) 每個處理器每次向 HB寫入一個 k-項集信息時，首先必須互斥地獲得一個表項地址，所以對HB表尾的一次排他訪問是不可避免的，將 k-項集的全體定義為一個視圖，可以直接保證這個排他訪問．另外由于向 HB中寫入的信息相對較少，只有 3個數(shù)據(jù)，所以不會形成嚴重的計算瓶頸．

(3) 每個項集相關(guān)的事務(wù)數(shù)目相對較多，特別是在 k值較小時更是如此，為了提高算法的并行度，應(yīng)該允許多個處理器同時生成各自的事務(wù)鏈．所以每個事務(wù)鏈定義為一個視圖．

圖3 視圖劃分結(jié)果Fig.3 Division of views

2.3 任務(wù)分配方案

算法的執(zhí)行分成 2個階段：第 1階段，2次掃描數(shù)據(jù)庫，第1次生成事務(wù)長度表LB，第2次生成頻繁1-項集和對應(yīng)的事務(wù)細節(jié)表；第 2階段，生成頻繁 k-項集．第1階段采用靜態(tài)任務(wù)分配策略，設(shè)有n個處理器，則把任務(wù)平均劃分成 n個，各處理器各自生成一部分頻繁 1-項集．在算法的第 2階段，設(shè)系統(tǒng)中有n個處理器，m 個(k-1)-項集．則每次生成 k-項集的任務(wù)劃分成 m-1個，任務(wù) i(i＝1，2，…，m-1)對應(yīng)第 i個(k-1)-項集與第 j個(k-1)-項集的連接，其中j＝i+1，i+2，…，m．所有處理器在生成 k-項集開始之前同步，并將全部(k-1)-項集放到本地的局部數(shù)據(jù)對象上，每次處理器 p取到一個任務(wù)并完成之后，將本次得到的k-項集加入HB．

顯然，隨著 i的增加，第 i個(k-1)-項集的連接對象有 m-i個，任務(wù)的計算量逐漸減少．另外由于一個任務(wù)連接生成的項集不一定是頻繁的，即一個任務(wù)中是否包含支持度計數(shù)和寫回全局 FI-list是不確定的，所以任務(wù)的大小是未知的．在任務(wù)數(shù)量和每個任務(wù)的大小都是動態(tài)確定的情況下，為了保持各個進程之間的負載平衡，這個階段采用動態(tài)任務(wù)分配．采用任務(wù)池模型，定義一個讀寫視圖 V，用于控制任務(wù)分配．V的值對應(yīng)當前任務(wù)編號，取值范圍[1，m-1]．處理器在取到一個任務(wù)之后，對V執(zhí)行增1操作．

2.4 算法描述

算法的第 1階段比較簡單，這里不再詳細描述，下面給出算法第2階段的描述．

對于系統(tǒng)中的第i個節(jié)點，

輸入：FI-list中的(k-1)-項集以及相關(guān)事務(wù)鏈表；最小支持度min_sup；

3 實驗結(jié)果及分析

3.1 實驗結(jié)果

實驗所用的集群由16臺運行Red Hat Linux9.0的個人計算機構(gòu)成，通過100,Mb/s交換機連接．每臺計算機帶有 650,MHz的處理器和 128 M 內(nèi)存，硬盤16,G，虛擬頁面大小為4,kB．實驗所用的數(shù)據(jù)庫是某超市的銷售數(shù)據(jù)庫，共 250,850條事務(wù)，所賣商品劃分為107個類別，有用數(shù)據(jù)量約為20%，實驗用來發(fā)現(xiàn)這些商品類別在銷售中的關(guān)系．

實驗分別做了3個方面的研究：①為了考察PMFSD在處理節(jié)點增加情況下的可擴展性能，在數(shù)據(jù)量和最小支持度不變、節(jié)點個數(shù)變化情況下計算算法的加速比；②為了觀察PMFSD算法對數(shù)據(jù)量的可擴展能力，在節(jié)點數(shù)量確定為8、支持度確定為1%，事務(wù)數(shù)量變化情況下計算算法的運行時間；③為了觀察PMFSD算法對數(shù)據(jù)源稀疏程度的適應(yīng)能力，采用隨機生成的二元矩陣(事務(wù)200,000條，項目50個)，在支持度確定為1%，數(shù)據(jù)稀疏程度不同情況下比較PMFSD算法的運行時間．為了對比算法的性能，選擇了MLFPT算法[5]，MLFPT也是在共享存儲結(jié)構(gòu)下實現(xiàn)的，在系統(tǒng)結(jié)構(gòu)上具有可比性．實驗結(jié)果見圖4～圖6．

圖4 PMFSD的加速比Fig.4 Speedup of PMFSD on VODCA

圖5 事務(wù)量變化運行時間Fig.5 Running time on different number of transactions

圖6 稀疏度變化運行時間Fig.6 Running time on different sparse data sources

3.2 結(jié)果分析

圖 4的實驗結(jié)果顯示加速比在處理器數(shù)目小于8時基本保持線性增長，但是在 16個處理器時增加幅度減?。@是因為處理器增多時系統(tǒng)中存在的同步消息增多，對共享數(shù)據(jù)的競爭加劇，這個情況可能會隨著問題規(guī)模的變化而有所變化．圖5顯示當處理的事務(wù)數(shù)量增加時，2種算法的運行時間比較．PMFSD運算效率呈先增加后降低的趨勢，在150,000條數(shù)據(jù)左右，效率最高，之后開始下降．開始效率增加是因為隨著計算量的增大，計算/通信比增加．而數(shù)據(jù)量增大的同時，每個節(jié)點上的內(nèi)存需求增大，特別是在支持度較小時，頻繁 1-項集和頻繁 2-項集的數(shù)量都很大，可能由于缺頁中斷，而使得計算速度下降．同樣，數(shù)據(jù)稀疏程度的變化也會產(chǎn)生類似情況．這種情況也能從圖 6所示的實驗結(jié)果中得到驗證，數(shù)據(jù)集越稀疏，與每個項目相關(guān)的事務(wù)數(shù)目越少，相關(guān)的交易鏈長度越?。ǔＴ陬l繁2-項集之后，隨著頻繁項集長度的增加，相關(guān)的事務(wù)數(shù)目急劇減少，整個鏈表的尺寸很小，容易裝入內(nèi)存，所以計算速度很快．當非零數(shù)據(jù)增多時，由于鏈結(jié)構(gòu)的開銷，整個鏈表尺寸實際上會大于相應(yīng)的二元數(shù)據(jù)庫，需要駐留本地內(nèi)存的數(shù)據(jù)增多，處理換頁的開銷達到一定比例，就會致使計算速度下降．采用MLFPT算法時，數(shù)據(jù)源越稀疏，F(xiàn)P-tree上的共享前綴越少，產(chǎn)生的 FP-tree也就越大，在生成 FP-tree和計算條件模式庫時會明顯增加掃描時間，從圖 6可以看出，2種算法隨數(shù)據(jù)源稀疏度變化的運算時間對比非常顯著．

算法的執(zhí)行時間由4個部分組成：系統(tǒng)啟動時間tstart，掃描數(shù)據(jù)庫所需時間 tscan，連接和依照單調(diào)性剪枝時間 tconn，計算支持數(shù)和寫入鏈表信息所需時間tlist．其中 tstart由系統(tǒng)確定．掃描數(shù)據(jù)庫時間 tscan涉及到實際計算時間和數(shù)據(jù)裝入本地所需的通信時間，可以描述為數(shù)據(jù)規(guī)模的線性函數(shù)，不對性能評價產(chǎn)生影響．頻繁 k-項集的數(shù)目與最小支持度和項目數(shù)有關(guān)，當數(shù)據(jù)源為稀疏數(shù)據(jù)源時，頻繁2-項集之后的頻繁項集數(shù)目會急劇減少，tconn主要發(fā)生在頻繁 3-項集產(chǎn)生之前，當頻繁項集數(shù)目增加時，HB的尺寸增大，連接和剪枝操作會導(dǎo)致更多的換頁，換頁概率正比于頻繁項集數(shù)目．項集的支持數(shù)計數(shù)和寫入事務(wù)細節(jié)的時間 tlist與事務(wù)數(shù)目和數(shù)據(jù)稀疏度有關(guān)，當與一個頻繁項集相關(guān)的事務(wù)數(shù)目較大時，tlist中的缺頁處理時間比例上升．以上4部分中影響算法效率的主要因素是 tconn和 tlist．若處理器數(shù)目確定，頁面尺寸為 M，處理缺頁中斷所需時間用 tf表示，事務(wù)數(shù)目為 N，最小支持度閾值為S，這2部分時間描述為

式中：hi是頻繁 i-項集的數(shù)目；ti為產(chǎn)生一個 i-項集所需的連接和依照單調(diào)性剪枝時間；tij是對第 j個 i-項集進行統(tǒng)計支持度和寫入鏈表時間；B1、B2是與編程有關(guān)的數(shù)據(jù)長度．

在只增加挖掘數(shù)據(jù)源中事務(wù)數(shù)量 N的情況下，式(1)的值是固定不變的，圖 5中性能下降的因素是式(2)．而圖 6性能下降的因素則包括式(1)和式(2)2部分，在支持度不變的情況下，有用數(shù)據(jù)量的增加，使得產(chǎn)生的頻繁項集數(shù)目顯著增加，從而大幅地提高了運算時間．

4 結(jié) 語

本文在一個新的分布式共享內(nèi)存編程環(huán)境VODCA上，針對稀疏數(shù)據(jù)源上的頻繁項集搜索問題，提出和實現(xiàn)了一個新的算法PMFSD，并通過實驗驗證了算法的有效性．PMFSD算法同樣可以在消息傳遞平臺上實現(xiàn)，實現(xiàn)的關(guān)鍵是FI-list的構(gòu)建．

［1］ Agrawal R，Srikant R. Fast algorithms for mining association rules in large databases[C]//Proceedings of20th International Conference on Very Large Data Bases(VLDB'94)．Santiago de Chile，Chile：Morgan Kaufmann，1994：489-499.

［2］ Han Jiawei，Pei Jian，Yin Yiwen. Mining frequent patterns without candidate generation[C]//Proceedings of the ACM SIGMOD Conference on Management ofData(SIGMOD'00)．New York：ACM Press，2000：1-12．

［3］ Agrawal R，Shafer J C．Parallel mining of association rules[J].IEEE Trans on Knowledge and Data Engineering，1996，8(6)：962-969.

［4］ Park J S，Chen M，Yu P S. Efficient parallel data mining for association rules[C]//ACM Intl Conf of Information and Knowledge Management．New York：ACM Press，1995：31-36．

［5］ Za?ane O R，El-Hajj M，Lu P. Fast parallel association rule mining without candidacy generation[C]//Proceedings of the2001IEEE International Conference on Data Mining. San Jose，USA：IEEE Computer Society，2001：665-668.

［6］ 陳惠萍，王建東，葉飛躍，等. 基于 FP-tree和支持度數(shù)組的最大頻繁項集挖掘算法[J]. 系統(tǒng)工程與電子技術(shù)，2005，27(9)：1631-1635.

Chen Huiping，Wang Jiandong，Ye Feiyue，et al. Efficient mining maximal frequent itemsets by using FP-tree and support array[J].Systems Engineering and Electronics，2005，27(9)：1631-1635(in Chinese).

［7］ 徐維祥，蘇曉軍. 基于頻繁模式樹的一種關(guān)聯(lián)規(guī)則挖掘算法及其在鐵路隧道安全管理中的應(yīng)用[J]. 中國安全科學(xué)學(xué)報，2007，17(3)：25-32.

Xu Weixiang，Su Xiaojun. A high-performance association rule mining algorithm based on FP-tree and its application in railway tunnel safety management[J].China Safety Science Journal(CSSJ)，2007，17(3)：25-32(in Chinese)．

［8］ Huang Z，Purvis M，Werstein P. View-Oriented Parallel Programming and View-Based Consistency[R]. Technical Report(OUCS-2004-09)，Dept of Computer Science，Univ of Otago，2004.

［9］ Huang Z，Chen W，Purvis M，et al. VODCA：Vieworiented，distributed，cluster-based approach to parallel computing[C]//Proc of the IEEE/ACM Symposium on Cluster Computing and Grid2006(CCGrid06)．Singapore：IEEE Computer Society，2006：15-28.

［10］ Huang Z，Purvis M，Werstein P. View oriented update protocol with integrated diff for view-based consistency[C]//Proc of the Fifth IEEE International Symposium on Cluster Computing and Grid2005(CCGrid′05)．Cardiff，UK：IEEE Computer Society，2005(2)：873-880．