沈榮 張保文

摘要： 首先針對數(shù)據(jù)分析中數(shù)據(jù)庫處理方式的不同，對數(shù)據(jù)倉庫的各種應(yīng)用場景，數(shù)據(jù)挖掘技術(shù)的處理過程和數(shù)據(jù)挖掘面臨的主要問題進(jìn)行了闡述；隨后對大數(shù)據(jù)處理技術(shù)的九種典型方法進(jìn)行了簡要綜述， 包括布隆過濾器、散列法、倒排序、數(shù)據(jù)庫索引與分布式處理等，對各種技術(shù)在大數(shù)據(jù)分析理解過程中的關(guān)鍵作用進(jìn)行了總結(jié)；并對大數(shù)據(jù)處理和分析面臨的計算復(fù)雜性、數(shù)據(jù)復(fù)雜性、以及系統(tǒng)復(fù)雜性進(jìn)行分析，對各種典型的業(yè)務(wù)應(yīng)用場景，提出了較為理想的應(yīng)對方案。

關(guān)鍵詞：數(shù)據(jù)庫；到排序；分布式處理； 數(shù)據(jù)挖掘； 大數(shù)據(jù)；推薦系統(tǒng)

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2019）11-0013-04

“人類自有史以來的數(shù)據(jù)總量，每過18個月就會翻番”——“新摩爾定律”。谷歌是大數(shù)據(jù)處理的鼻祖，早在2007年，谷歌每天就要處理近20PB的數(shù)據(jù)量。2011年，全球數(shù)據(jù)總量就已達(dá)到了2.1ZB。IDC預(yù)計到2020年，全球數(shù)據(jù)總量將會超過40ZB。我國也在各個領(lǐng)域出現(xiàn)了海量數(shù)據(jù)。2013年百度的數(shù)據(jù)總量接近1000PB，阿里巴巴公司保存的數(shù)據(jù)超過了百PB級別，騰訊公司總存儲數(shù)據(jù)量經(jīng)壓縮處理后仍超過了百PB級別，并且數(shù)據(jù)月增量達(dá)到10%，包括大量社交、游戲等領(lǐng)域積累的文本、音頻、視頻和關(guān)系類數(shù)據(jù)，大數(shù)據(jù)應(yīng)用系統(tǒng)覆蓋數(shù)據(jù)的獲取、清洗、集成、分析與可視化等大數(shù)據(jù)全生命周期的多個處理環(huán)節(jié)[1]。伴隨信息技術(shù)的發(fā)展，人們逐步邁入了大數(shù)據(jù)時代[2-6]的人-機-物融合的三元世界。近年來，大數(shù)據(jù)引起了學(xué)術(shù)界和產(chǎn)業(yè)界谷歌[7]等的重視，政府部門如美國[8]和其他組織如麥肯錫公司[9]、高德納公司[10]的高度關(guān)注。

1 大數(shù)據(jù)分析

大數(shù)據(jù)技術(shù)是隨著數(shù)據(jù)量急劇膨脹而產(chǎn)生的對海量數(shù)據(jù)使用和提取有效信息的一種方法，數(shù)據(jù)倉庫是大數(shù)據(jù)分析的基礎(chǔ)，數(shù)據(jù)挖掘是建立數(shù)據(jù)倉庫的方法，也是使用和分析數(shù)據(jù)的方法。

1.1數(shù)據(jù)倉庫

Oracle、Mysql、SQL server等關(guān)系數(shù)據(jù)庫管理系統(tǒng)是隨著關(guān)系數(shù)據(jù)庫理論的提出現(xiàn)的，隨著數(shù)據(jù)庫使用范圍的不斷擴大，逐步被分為操作型數(shù)據(jù)庫和分析型數(shù)據(jù)庫。

1.1.1操作型數(shù)據(jù)庫與分析型數(shù)據(jù)庫的區(qū)別

（1）數(shù)據(jù)組成差別

操作型數(shù)據(jù)一般只會存放90天以內(nèi)的數(shù)據(jù)，主要存放細(xì)節(jié)數(shù)據(jù)，一般反映的是現(xiàn)實世界的當(dāng)前狀態(tài)。分析型數(shù)據(jù)庫存放的則是數(shù)年內(nèi)的數(shù)據(jù)，既有細(xì)節(jié)數(shù)據(jù)，又有匯總數(shù)據(jù)，一般用戶關(guān)注的是匯總數(shù)據(jù)部分，它可以綜合所有快照對各個歷史階段進(jìn)行統(tǒng)計分析。

（2）技術(shù)差別

操作型數(shù)據(jù)庫查詢的數(shù)據(jù)量少但頻率高，并且允許用戶進(jìn)行增加、刪除、修改、查詢的操作，可以減少數(shù)據(jù)冗余，避免更新異常；而分析型數(shù)據(jù)庫查詢的量大但頻率少，并且只能允許進(jìn)行查詢，它并不重視減少數(shù)據(jù)冗余。

1.1.2 數(shù)據(jù)倉庫的組成

數(shù)據(jù)倉庫的核心組件主要由四部分組成：各個源數(shù)據(jù)庫、數(shù)據(jù)倉庫技術(shù)（ETL）、數(shù)據(jù)倉庫和前端應(yīng)用，如圖1所示：

（1）業(yè)務(wù)系統(tǒng)

業(yè)務(wù)系統(tǒng)包括各種源數(shù)據(jù)庫，這些源數(shù)據(jù)庫主要為業(yè)務(wù)系統(tǒng)提供數(shù)據(jù)支撐，同時也可以作為數(shù)據(jù)倉庫的數(shù)據(jù)源，當(dāng)然，除了業(yè)務(wù)系統(tǒng)，數(shù)據(jù)倉庫也可以從其他外部數(shù)據(jù)源獲取數(shù)據(jù)。

（2）ETL

ETL過程是構(gòu)建數(shù)據(jù)倉庫的重要的一個環(huán)節(jié)，包括數(shù)據(jù)提?。‥xtract）、轉(zhuǎn)換（tranform）、清洗（cleansing）、加載（load）。

（3）數(shù)據(jù)倉庫

數(shù)據(jù)倉庫的突出的特點是對海量數(shù)據(jù)的支持和快速的檢索技術(shù)。

1.2數(shù)據(jù)挖掘

數(shù)據(jù)挖掘既是建立數(shù)據(jù)倉庫的方法，也是使用和分析數(shù)據(jù)的方法，數(shù)據(jù)挖掘在大型數(shù)據(jù)存儲庫中，可以自動發(fā)現(xiàn)有用的信息。數(shù)據(jù)挖掘用來探查大型數(shù)據(jù)庫，發(fā)現(xiàn)先前未知的有用的模式。

數(shù)據(jù)挖掘是數(shù)據(jù)庫中知識發(fā)現(xiàn)（Knowledge Discovery in database，Kdd）不可缺少的一部分，而KDD是將未加工的數(shù)據(jù)轉(zhuǎn)換為有用信息的整個過程，該過程包括一系列轉(zhuǎn)換步驟，從數(shù)據(jù)的預(yù)處理到數(shù)據(jù)挖掘結(jié)果的后處理。

數(shù)據(jù)挖掘主要任務(wù)包括預(yù)測建模（Predictive Modeling）、關(guān)聯(lián)分析、聚類分析、異常檢測等。

2 大數(shù)據(jù)處理方法

對于海量數(shù)據(jù)的處理，手工方式早已不能滿足需求，必須通過工具進(jìn)行處理。當(dāng)數(shù)據(jù)量達(dá)到TB級別時，用計算機處理時也會對軟、硬件的要求加倍提升。當(dāng)遇到的海量數(shù)據(jù)無法全部存入內(nèi)存時，那么如何處理這些重復(fù)、格式不正確的數(shù)據(jù)也是數(shù)據(jù)處理人員需要去解決的問題。

2.1 布隆過濾器及散列法

布隆過濾器（Bloom Filter）是1970年由Bloom提出，最初廣泛用于拼寫檢查和數(shù)據(jù)庫系統(tǒng)中。

布隆過濾器的基本原理：當(dāng)一個元素被加入集合時，通過k個散列函數(shù)將這個元素映射為一個元素中的k個點，把它們置為1。檢索時，我們只要看這些點是否是1就知道集合中是否有它了。如果這些點有任何一個0，則被檢元素一定不在；如果都是1，被檢元素很可能在，查找結(jié)果并不能保證100%正確。所以簡單的改進(jìn)就是Counting Bloom Filter，用counter數(shù)組代替位數(shù)組，就可以支持刪除了插入的關(guān)鍵字了。

原始的Bloom Filter不支持刪除已經(jīng)插入的關(guān)鍵字，因為該關(guān)鍵字對應(yīng)的位會牽動到其他關(guān)鍵字。所以簡單的改進(jìn)就是Counting Bloom Filter，用counter數(shù)組代替位數(shù)組，就可以支持刪除了插入的關(guān)鍵字了。布隆過濾器可以用來實現(xiàn)數(shù)據(jù)字典，進(jìn)行數(shù)據(jù)的判重（重復(fù)數(shù)據(jù)判斷），或者集合求交集。

散列法（Hashing）是計算機科學(xué)中一種對數(shù)據(jù)的處理方法，通過某種特定的函數(shù)/算法，將要檢索的項與用來檢索的索引關(guān)聯(lián)起來，生成一種便于搜索的數(shù)據(jù)結(jié)構(gòu)。它常用作一種信息安全的方法，如果一串?dāng)?shù)據(jù)中經(jīng)過散列算法計算出來的數(shù)據(jù)指紋，經(jīng)常用來識別檔案與數(shù)據(jù)是否被篡改過，以保證檔案與數(shù)據(jù)確實是由原創(chuàng)者所提供的。

Hash函數(shù)選擇在針對字符串、整數(shù)、排列時具有相應(yīng)的Hash方法。 一種是Open Hashing，也稱為拉鏈法；另一種就是Closed Hashing，也稱開放地址法，即Opened Addressing。目前主要有除法散列法，平方散列法，斐波那契（Fibonacci）散列法。

2.2 堆排序及雙層桶劃分

堆排序（Heapsort）是利用一種叫堆積樹的數(shù)據(jù)結(jié)構(gòu)所設(shè)計出來的一種排序算法，它是選擇排序的一種，可以利用數(shù)組的特點快速定位指定索引的元素。堆分為大頂堆和小頂堆，是完全二叉樹.大頂堆的要求是每個節(jié)點的值都不大于其父節(jié)點的值。在數(shù)組的非降序排序中，需要使用的就是大頂堆，因為根據(jù)大頂堆的要求可知，最大值一定在堆頂。

利用大頂堆（小頂堆）項記錄的是最大關(guān)鍵字（最小關(guān)鍵字）這一特性，使得每次從無序數(shù)組中選擇最大記錄（最小記錄）變得簡單了。對于堆排序，最重要的兩個操作就是構(gòu)造初始堆和調(diào)整堆，事實上構(gòu)造初始堆就是調(diào)整堆的過程，但構(gòu)造初始堆是對所有非葉節(jié)點都進(jìn)行調(diào)整。

堆排序適合處理海量數(shù)據(jù)，并且是可以放入內(nèi)存的數(shù)據(jù)。

雙層桶劃分是一種數(shù)據(jù)結(jié)構(gòu)，也可以看作一種算法設(shè)計思想.面對一堆大量的數(shù)據(jù)無法處理的時候，可以將其分為一個個小的單元，然后根據(jù)一定的策略來處理這些小單元。從而達(dá)到目的。

因為元素范圍很大，不能利用直接尋址表，所以可通過多次劃分，逐步確定范圍，然后可以在一個可以接受的范圍內(nèi)進(jìn)行?？梢酝ㄟ^多次劃分來縮小范圍，雙層只是一個例子，分治才是其根本。

雙層桶劃分適用于數(shù)據(jù)庫范圍查詢，用來尋找第k大、中位數(shù)、不重復(fù)（或重復(fù)）的數(shù)字。

2.3索引

根據(jù)數(shù)據(jù)庫的功能，可在數(shù)據(jù)庫中創(chuàng)建3種索引：

（1）唯一索引

唯一索引是不允許其中任何兩行具有相同索引值的索引。當(dāng)現(xiàn)有數(shù)據(jù)中存在重復(fù)的鍵值時，大多數(shù)數(shù)據(jù)庫不允許將新創(chuàng)建的唯一索引與表一起保存。數(shù)據(jù)庫還可能防止添加將在表中創(chuàng)建重復(fù)值得新數(shù)據(jù)。

（2）主鍵索引

主鍵索引是唯一索引的特殊類型，主鍵索引要求主鍵中的每個值都唯一，當(dāng)在查詢中使用主鍵索引時，還允許對數(shù)據(jù)的快速訪問。

（3）聚集索引

聚集索引中表中的物理順序與鍵值的邏輯索引順序是一樣的，一張表只能包含一個聚集索引，如果某索引不是聚集索引，那么表中行的物理順序與鍵值的邏輯順序是不匹配的，聚集索引比非聚集索引將提供更快的數(shù)據(jù)訪問速度。

數(shù)據(jù)庫索引是數(shù)據(jù)庫管理系統(tǒng)中一個排序的數(shù)據(jù)結(jié)構(gòu)，可以提高數(shù)據(jù)庫表的數(shù)據(jù)訪問速度，能實現(xiàn)大數(shù)據(jù)量的增加、刪除、修改、查詢等操作，還可以實現(xiàn)快速查詢、更新數(shù)據(jù)庫表中的數(shù)據(jù)。

倒排序索引在實際應(yīng)用中主要是根據(jù)屬性的值來查找數(shù)據(jù)，是根據(jù)屬性來確定記錄的位置，而不是由記錄來確定屬性值。這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址，帶有倒排序索引的文件稱為倒排索引文件，也稱倒排文件。

倒排序索引是文檔檢索系統(tǒng)中最常用的數(shù)據(jù)結(jié)構(gòu)，主要用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。倒排序索引可以根據(jù)單詞快速獲取包含這個單詞的文檔列表，是實現(xiàn)單詞到文檔映射關(guān)系的最佳實現(xiàn)方式和最有效地索引結(jié)構(gòu)，主要適用于搜索引擎、關(guān)鍵字查詢等。

2.4 外排序及TRIE樹

外排序指的是對大文件的排序，當(dāng)文件太大而無法將整個文件所有記錄調(diào)入內(nèi)存中進(jìn)行排序時，只能將文件放在外存儲器中，通過數(shù)據(jù)的內(nèi)、外存交換和”內(nèi)部歸并”兩者結(jié)合起來實現(xiàn)。外排序在排序期間由于文件太大對象個數(shù)太多，不能同時全部存入內(nèi)存，因此必須根據(jù)排序過程的要求，在內(nèi)、外存之間不斷地進(jìn)行移動排序，適用于大部分大數(shù)據(jù)的排序、去重。

單詞查找樹Trie是一種哈希樹的變種，也是一種樹形結(jié)構(gòu)。

TRIE樹在信息檢索、字符串匹配等領(lǐng)域有廣泛的應(yīng)用，是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，它也是后綴樹、 AC自動機等復(fù)雜算法和數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。

本節(jié)將分析對比典型的大數(shù)據(jù)處理平臺，如 Hadoop[11]， Disco[12]，Twister[13]，Haloop[14]，iMapReduce[15]，iHadoop[16]以及類似MapReduce的Dryad[17]，Spark[18]。

3 大數(shù)據(jù)分析業(yè)務(wù)場景

3.1 信用風(fēng)險建模

在信用風(fēng)險建模中，可以根據(jù)實際需求采用多種不同的分析建模技術(shù)。在信用風(fēng)險建模中，需要計算的其他指標(biāo)還有違約損失率（LGD）、違約風(fēng)險暴露（Exposure at Default，EAD）。違約損失率（LGD）是以未償貸款總金額占比的形式來衡量經(jīng)濟損失，通常以線性回歸方法或回歸樹方法進(jìn)行估算。EAD是指債務(wù)人違約時預(yù)期的表外項目和表內(nèi)項目的風(fēng)險暴露總額，如抵押貸款、分期償還的借款等，表外項目指信用卡的信用額度、賒銷最高限額等。

3.2 產(chǎn)品知識中心

產(chǎn)品提供商創(chuàng)建的知識中心，可以直接在網(wǎng)站中使用，通過將信息放在WEB上，通信服務(wù)提供商網(wǎng)站作為知識中心，可以增加網(wǎng)站流量并減少投訴人數(shù)，知識中心網(wǎng)站提供自助服務(wù)，用戶需要的產(chǎn)品支持技術(shù)通過知識中心自助解決，所以客戶需要產(chǎn)品服務(wù)時，聯(lián)系呼叫中心，尋求產(chǎn)品技術(shù)幫助的來源減少了。

一旦創(chuàng)建了一個知識的來源，這個來源可用于銷售其他產(chǎn)品，并且把產(chǎn)品的特點和用戶的訴求連接起來。許多關(guān)于該產(chǎn)品的零散的知識可能會迅速組織起來，并找到各種其他用途。

3.3 基于位置的服務(wù)

使用大數(shù)據(jù)技術(shù)的交易數(shù)據(jù)分析是革命性的，基于位置的服務(wù)，實現(xiàn)了個性化服務(wù)，完成了低延時導(dǎo)購服務(wù)。Shopkick是一個零售活動的工具，可以下載到任意一部智能手機上。SHopkick需要使用位置數(shù)據(jù)以提供服務(wù)。一旦該應(yīng)用程序被下載到智能手機中，SHOPkick 將會尋找可使用的用戶，通過智能手機記錄他們的當(dāng)前位置。此外，Shopkick還有零售商及其地理位置數(shù)據(jù)庫。當(dāng)用戶家附近的百貨商場想讓用戶去購物并激發(fā)購物欲望，Shopkick會給用戶獎勵這家商場的購物優(yōu)惠券。當(dāng)用戶走進(jìn)商場時，Shopkick可以使用智能手機確認(rèn)當(dāng)前的位置在該商場，然后增加用戶的積分獎勵，從而為用戶換取更大的優(yōu)惠。

設(shè)備制造商、通信服務(wù)提供商都已經(jīng)開始提供大量的基于位置的服務(wù)，以吸引用戶。例如智能手機在提供”找到我的電話”服務(wù)，可以找到電話。如果手機丟失，可以通過網(wǎng)站確定最后的已知的位置。這些基于位置的服務(wù)也可以產(chǎn)生收入。通信服務(wù)提供商可以決定為每次將智能手機切換到靜音模式的配置服務(wù)收費。用戶進(jìn)入電影院后切換到靜音模式，一旦用戶離開電影院，就自動恢復(fù)正常響鈴。使用這些數(shù)據(jù)的時候，一定要考慮如何保護(hù)用戶隱私。

3.4 推薦系統(tǒng)

推薦系統(tǒng)作為一種有效的信息過濾手段，是當(dāng)前解決信息過載問題及實現(xiàn)個性化信息服務(wù)的有效方法之一。目前，主流推薦系統(tǒng)可以分為 4 類[19]：協(xié)同過濾推薦、基于內(nèi)容的推薦、基于知識的推薦和組合推薦。

3.5 市場細(xì)分

自動化技術(shù)讓我們有機會在面向客戶流程的每一步中收集數(shù)據(jù)在網(wǎng)頁上的行為，例如，單擊網(wǎng)站中的點擊流。傳感器的數(shù)據(jù)給了我們一個建立行為學(xué)模式應(yīng)用分析的機會。早期的技術(shù)化是使用分析法來進(jìn)行市場細(xì)分，原始的細(xì)分方式使用了人口統(tǒng)計學(xué)技術(shù)，并使用消費者的硬數(shù)據(jù)，如地理位置、年齡、性別和名族特點，建立市場細(xì)分。但營銷人員很快意識到，行為特征也是細(xì)分客戶的重要參數(shù)。

隨著市場的發(fā)展，可以看到更多、更細(xì)致的細(xì)分方式，基于分析參數(shù)，驅(qū)動特定市場。例如，對于小型電子產(chǎn)品，市場營銷人員開始嘗試區(qū)分以下兩類人群：一類是由于愿意嘗試新鮮事物而購買的創(chuàng)新者，一類是跟隨其他人購買的適應(yīng)者。通過數(shù)據(jù)分析表可知，創(chuàng)新者群體樂于早期分享使用產(chǎn)品經(jīng)驗，而且對產(chǎn)品的缺陷表現(xiàn)得更寬容。

3.6 在線廣告

隨著在線內(nèi)容的發(fā)布，線上廣告在市場上的影響越來越大，同時，在線廣告變得越來越復(fù)雜，為細(xì)分市場廣告和基于上下文的廣告提供了巨大的機會。發(fā)布客戶廣告的主要目標(biāo)是在適當(dāng)?shù)木W(wǎng)頁上下文環(huán)境下，打動線上的用戶，從而使用戶產(chǎn)生行動，實現(xiàn)對商品的購買。大數(shù)據(jù)為營銷人員提供了一個機會：收集無數(shù)用戶的行為信息。通過整理和分析這些信息，可以建立兩套關(guān)于客戶的見解，這兩項都與在線廣告相關(guān)。首先，通過細(xì)分大量用戶的購物歷史來建立用戶細(xì)分段，以及每個段的習(xí)慣購買模式。其次，可以使用上下文的驅(qū)動，特定于上下文的廣告。

4 小結(jié)

本文主要介紹了大數(shù)據(jù)發(fā)展中出現(xiàn)的各種發(fā)展技術(shù)，介紹了布隆過濾器、散列法、堆排序、雙層桶劃分、數(shù)據(jù)庫索引、倒排索引、外排序、trie樹、分布式處理九種不同形式數(shù)據(jù)，并對信用分險建模、基于位置的服務(wù)、推薦系統(tǒng)、市場細(xì)分、在線廣告五類大數(shù)據(jù)分析應(yīng)用場景進(jìn)行了介紹。

參考文獻(xiàn)：

[1] Jagadish HV， Gehrke J， Labrinidis A， Papakonstantinou Y， Patel JM， Ramakrishnan R， Sha-habi C. Big data and its technical. Communications of the Acm， 2014.

[2] Big data. Nature， 2008，455（7209）：1-136.

[3] Dealing with data. Science， 2011，331（6018）：639-806.

[4] Big data. ERCIM News， 2012（89）：10-39.

[5] Vivien Marx. The big challenges of big data. Nature， 2013， 498（7453）：255-260.

[6] Xindong Wu， Xingquan Zhu， Gong-Qing Wu， and Wei Ding. Data mining with big data. IEEE Transactions on Knowledge and Data Engineering， 2014，26（1）：97-107.

[7] Divyakant Agrawal， Philip Bernstein， Elisa Bertino， Susan Davidson， Umeshwar Dayal， Mi-chael Franklin， Johannes Gehrke， Laura Haas， Alon Halevy， Jiawei Han， H.V. Jagadish， Alexandros Labrinidis， Sam Madden， Yannis Papakonstantinou， Jignesh Patel， Raghu Ramakrish-nan， Kenneth Ross， Cyrus Shahabi， Dan Suciu， Shiv Vaithyanathan， and Jennifer Widom. Chal-lenges and opportunities with big data： A community white paper developed by leading research-ers across the united states. White Paper， 2012.

[8] Rick Weiss and Lisa-Joy Zgorski. Obama administration unveils “Big Data” initiative： An-nounces $200 million in new R&D investments. Office of Science and Technology Policy， Executive Office of the President， 2012.

[9] James Manyika， Michael Chui， Brad Brown， Jacques Bughin， Richard Dobbs， Charles Roxburgh， and Angela Hung Byers. Big data： The next frontier for innovation， competition， and productivity. McKinley Global Institute， White Paper， 2011.

[10] Yvonne Genovese and Stephen Prentice. Pattern-based strategy： Getting value from big data. Gartner Secial Report， G00214032， 2011.

[11] Liu Y， Li M， Alham NK， Hammoud S. HSim： A MapReduce simulator in enabling cloud computing. Future Generation Computer Systems， 2013，29（1）：300 308. [doi： 10.1016/j.future.2011.05.007].

[12] GridGain in-memory data fabric. http：//go.gridgain.com/rs/491-TWR-806/images/GridGain_Product_Datasheet_070416.pdf.

[13] Mundkur P， Tuulos V， Flatow J. Disco： A computing platform for large-scale data analytics. In： Proc. of the 10th ACM SIGPLAN Workshop on Erlang. 2011. 84 89. [doi： 10.1145/2034654.2034670]540 Journal of Software Vol.28， No.3， March 2017.

[14] Ekanayake J， Li H， Zhang B， Gunarathne T， Bae S， Qiu J， Fox G. Twister： A runtime for iterative MapReduce. In： Proc. of the 19th ACM Intl Symp. on High Performance Distributed Com-puting. ACM Press， 2010. 810 818. [doi： 10.1145/1851476.1851593].

[15] Bu Y， Howe B， Balazinska M， Ernst MD. HaLoop： Efficient iterative data processing on large clusters. Proc. of the VLDB Endowment， 2010，3（1-2）：285 296. [doi： 10.14778/1920841.1920881].

[16] Zhang Y， Gao Q， Gao L， Wang C. Imapreduce： A distributed computing framework for iterative computation. Journal of Grid Computing， 2012，10（1）：47 68. [doi： 10.1007/s10723-012-9204-9].

[17] Elnikety E， Elsayed T， Ramadan HE. iHadoop： Asynchronous iterations for MapReduce. In： Proc. of the 3rd IEEE Intl Conf. on Cloud Computing Technology and Science （CloudCom）. IEEE， 2011. 81 90. [doi： 10.1109/CloudCom.2011.21].

[18] Isard M， Budiu M， Yu Y， Birrell A， Fetterly D. Dryad： Distributed data-parallel programs from sequential building blocks. Proc. Of the ACM SIGOPS Operating Systems Review， 2007，41（3）：59 72. [doi： 10.1145/1272998.1273005].

[19] Zaharia M， Chowdhury M， Franklin MJ， Shenker S， Stoica I. Spark： Cluster computing with working sets. HotCloud， 2010.

【通聯(lián)編輯：唐一東】