大數(shù)據(jù)基礎(chǔ)理論與系統(tǒng)關(guān)鍵技術(shù)淺析

華強(qiáng)勝，鄭志高，胡振宇，鐘芷漫，林昌富，趙峰，金海＊，石宣化

1.大數(shù)據(jù)技術(shù)與系統(tǒng)國(guó)家地方聯(lián)合工程研究中心，湖北 武漢 430074

2.服務(wù)計(jì)算技術(shù)與系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074

3.集群與網(wǎng)格計(jì)算湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074

4.華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430074

引言

大數(shù)據(jù)具有多樣性、快速性和大規(guī)模等特點(diǎn)，傳統(tǒng)算法與系統(tǒng)面對(duì)大數(shù)據(jù)的復(fù)雜應(yīng)用場(chǎng)景具有很大挑戰(zhàn)性。大數(shù)據(jù)基礎(chǔ)理論以及大數(shù)據(jù)的存儲(chǔ)、檢索、分析和挖掘等技術(shù)，為大數(shù)據(jù)的廣泛高效應(yīng)用提供技術(shù)支持。本文基于“大數(shù)據(jù)快速存儲(chǔ)與計(jì)算環(huán)境”、“高通量計(jì)算與近似計(jì)算的理論與算法”等國(guó)家重點(diǎn)研發(fā)計(jì)劃課題；“面向大數(shù)據(jù)的高時(shí)效并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)與技術(shù)”、“大規(guī)模圖中圖性質(zhì)求解的低復(fù)雜度分布式算法研究”等國(guó)家自然科學(xué)基金項(xiàng)目以及一批面向電子政務(wù)、航空運(yùn)輸?shù)葢?yīng)用處理平臺(tái)項(xiàng)目，對(duì)不同領(lǐng)域大數(shù)據(jù)問(wèn)題進(jìn)行簡(jiǎn)要介紹，并從算法、系統(tǒng)等多個(gè)維度介紹一系列的典型系統(tǒng)、探討多個(gè)典型大數(shù)據(jù)領(lǐng)域數(shù)據(jù)處理問(wèn)題解決思路。

（1）在大數(shù)據(jù)理論方面，針對(duì)隱私保護(hù)數(shù)據(jù)聚合問(wèn)題，大部分已有協(xié)議只能針對(duì)某一種或者幾種統(tǒng)計(jì)函數(shù)，同時(shí)需要一個(gè)可信任的第三方。文獻(xiàn)[1]設(shè)計(jì)一種協(xié)議可以計(jì)算任意的統(tǒng)計(jì)函數(shù)并且保護(hù)隱私，同時(shí)該協(xié)議不需要可信任第三方的參與且具有較低的通信復(fù)雜度。

（2）在大數(shù)據(jù)處理方面，通過(guò)對(duì)數(shù)據(jù)并行應(yīng)用進(jìn)行觀察和分析，得出數(shù)據(jù)并行應(yīng)用的運(yùn)行過(guò)程具有階段性的結(jié)論。根據(jù)每個(gè)階段中任務(wù)的數(shù)據(jù)和數(shù)據(jù)分區(qū)的特點(diǎn)，文獻(xiàn)[2]研發(fā)了基于階段劃分的程序分析優(yōu)化器SDPA (Stage-Divided Program Analysis)。同時(shí)，針對(duì)I/O請(qǐng)求具有突發(fā)性并且在不同服務(wù)器上分配不均以及由于應(yīng)用的帶寬訪(fǎng)問(wèn)模式的限制使得I/O帶寬分配不合理導(dǎo)致系統(tǒng)整體性能下降的問(wèn)題，文獻(xiàn)[2]提出了一個(gè)通用的I/O帶寬控制方案。

（3）在大數(shù)據(jù)管理方面，針對(duì)SPARQL查詢(xún)語(yǔ)言復(fù)雜難懂以及無(wú)法在合理時(shí)間內(nèi)處理復(fù)雜查詢(xún)的特點(diǎn)，文獻(xiàn)[3]提出以自然語(yǔ)言為訪(fǎng)問(wèn)接口，設(shè)計(jì)了基于異構(gòu)圖模式近似匹配方法研究的自然語(yǔ)言問(wèn)答系統(tǒng)。同時(shí)還設(shè)計(jì)了共享內(nèi)存環(huán)境下圖查詢(xún)并行處理系統(tǒng)ParTriple[4]。

（4）在大數(shù)據(jù)分析方面，針對(duì)實(shí)際流處理應(yīng)用中，上下流任務(wù)在數(shù)據(jù)處理和任務(wù)恢復(fù)兩方面所具有的強(qiáng)依賴(lài)特性，給分布式流處理系統(tǒng)帶來(lái)了處理延遲高、吞吐率受限、恢復(fù)延時(shí)長(zhǎng)等嚴(yán)重問(wèn)題，文獻(xiàn)[5]研發(fā)了分布式流處理容錯(cuò)系統(tǒng)Ares。另一方面，為了衡量查詢(xún)語(yǔ)句與文檔之間的語(yǔ)義相關(guān)性，提出基于實(shí)體的語(yǔ)言模型平滑方法。文獻(xiàn)[6]還提出了符合文檔語(yǔ)義主題下單詞概率分布的實(shí)體語(yǔ)義語(yǔ)言模型，以及兩層次的平滑方法。

1 低復(fù)雜度隱私保護(hù)數(shù)據(jù)聚合算法研究

隱私保護(hù)數(shù)據(jù)聚合問(wèn)題是一直是應(yīng)用密碼學(xué)領(lǐng)域的研究熱點(diǎn)。在實(shí)際生活中有很多應(yīng)用，用戶(hù)需要提供他們敏感的數(shù)據(jù)到數(shù)據(jù)中心，數(shù)據(jù)中心根據(jù)收到的用戶(hù)數(shù)據(jù)計(jì)算相應(yīng)的統(tǒng)計(jì)函數(shù)，如最大值、最小值和平均數(shù)等。對(duì)于這個(gè)問(wèn)題，通常有兩個(gè)核心的挑戰(zhàn)需要解決，即通信開(kāi)銷(xiāo)與數(shù)據(jù)隱私。如何降低計(jì)算過(guò)程中通信開(kāi)銷(xiāo)和保護(hù)用戶(hù)數(shù)據(jù)隱私是該領(lǐng)域研究學(xué)者一直不懈探索的目標(biāo)[1]。

1.1 研究問(wèn)題

為解決上述問(wèn)題，文獻(xiàn)[1]采用One Aggregator模型，即在這個(gè)模型中，有一個(gè)不可信的聚合中心和n個(gè)用戶(hù)[1]。通過(guò)雙向的通信鏈路，聚合中心與每一個(gè)用戶(hù)可以互相發(fā)送消息。每個(gè)用戶(hù)定期會(huì)產(chǎn)生隱私的數(shù)據(jù)。根據(jù)用戶(hù)的隱私數(shù)據(jù)，聚合中心主要負(fù)責(zé)計(jì)算一些統(tǒng)計(jì)函數(shù)。文獻(xiàn)[1]假設(shè)聚合中心與用戶(hù)都是半誠(chéng)實(shí)的(Semi-honest)，即他們忠誠(chéng)的執(zhí)行協(xié)議，同時(shí)在運(yùn)行過(guò)程中想推測(cè)其他用戶(hù)的隱私數(shù)據(jù)(有好奇心)。他們彼此之間可以相互同謀，以便獲取其余參與方的隱私數(shù)據(jù)。假設(shè)聚合中心和k個(gè)用戶(hù)同謀，那么文獻(xiàn)[1]的研究問(wèn)題是在無(wú)可信任第三方情況下，聚合中心計(jì)算任意統(tǒng)計(jì)函數(shù)，同時(shí)保護(hù)用戶(hù)隱私和實(shí)現(xiàn)較低通信開(kāi)銷(xiāo)。

1.2 研究策略

根據(jù)以上問(wèn)題描述，可以看出為了使聚合中心可以計(jì)算任意統(tǒng)計(jì)函數(shù)，一個(gè)可行的方法就是直接收集所有用戶(hù)數(shù)據(jù)。然而用戶(hù)數(shù)據(jù)是隱私的，顯然用戶(hù)直接發(fā)送隱私數(shù)據(jù)到聚合中心的方式不可行。為此文獻(xiàn)[1]設(shè)計(jì)一個(gè)協(xié)議，在無(wú)可信任第三方情況下，聚合中心獲取所有用戶(hù)數(shù)據(jù)，同時(shí)保護(hù)隱私(即達(dá)到(n-k)-源匿名：對(duì)于未同謀用戶(hù)的數(shù)據(jù)，聚合中心不知道所收到的數(shù)據(jù)與用戶(hù)之間對(duì)應(yīng)的關(guān)系)和實(shí)現(xiàn)較低的通信開(kāi)銷(xiāo)。

為了保護(hù)用戶(hù)數(shù)據(jù)隱私，文獻(xiàn)[1]采用DH(Diffie-Hellman) 密鑰交換協(xié)議，使得每個(gè)用戶(hù)產(chǎn)生共享的密鑰集。根據(jù)所得密鑰集，每個(gè)用戶(hù)生成相應(yīng)的偽隨機(jī)函數(shù)。利用生成的偽隨機(jī)函數(shù)每個(gè)用戶(hù)對(duì)數(shù)據(jù)進(jìn)行加密。

為了降低通信開(kāi)銷(xiāo)，文獻(xiàn)[1]設(shè)計(jì)隨機(jī)抽樣與劃分技術(shù)使得每個(gè)用戶(hù)獲得唯一序列號(hào)。具體來(lái)說(shuō)，每個(gè)用戶(hù)在區(qū)間 [1,n^5 ]隨機(jī)抽樣一個(gè)隨機(jī)數(shù)，并將此區(qū)間劃分為n等長(zhǎng)的子區(qū)間。當(dāng)某個(gè)子區(qū)間所含隨機(jī)值數(shù)量是1時(shí)，聚合中心保存此子區(qū)間；當(dāng)某個(gè)子區(qū)間所含隨機(jī)值數(shù)量超過(guò)1但是小于時(shí)，聚合中心將此區(qū)間均勻劃分a2份；當(dāng)某個(gè)子區(qū)間所含隨機(jī)值數(shù)量大于時(shí)，聚合中心將此區(qū)間均勻劃分log3n份。聚合中心與用戶(hù)遞歸此過(guò)程，直到聚合中心保存的子區(qū)間的數(shù)量等于n。然后，聚合中心發(fā)送這n個(gè)子區(qū)間到所有用戶(hù)，每個(gè)用戶(hù)根據(jù)這n個(gè)子區(qū)間獲得自己的唯一序列號(hào)。最后根據(jù)唯一序列號(hào)，聚合中心獲取所有的用戶(hù)隱私數(shù)據(jù)。通過(guò)嚴(yán)格的理論證明，對(duì)于隱私保護(hù)問(wèn)題，文獻(xiàn)[1]設(shè)計(jì)的協(xié)議可以實(shí)現(xiàn)(n-k)-源匿名，同時(shí)該協(xié)議通信復(fù)雜度為

2 面向數(shù)據(jù)并行的大數(shù)據(jù)處理技術(shù)

2.1 SDPA：數(shù)據(jù)并行的應(yīng)用程序分析優(yōu)化器

在大數(shù)據(jù)處理系統(tǒng)中，數(shù)據(jù)并行應(yīng)用的性能變得越來(lái)越重要，這些應(yīng)用的性能和代碼邏輯與運(yùn)行時(shí)的資源利用有關(guān)。程序分析技術(shù)是一種常用的優(yōu)化應(yīng)用的方法，而且這項(xiàng)技術(shù)已經(jīng)被運(yùn)用到數(shù)據(jù)并行應(yīng)用中，但是目前還沒(méi)有一個(gè)能夠高效分析整體數(shù)據(jù)并行應(yīng)用的方法。

通過(guò)對(duì)數(shù)據(jù)并行應(yīng)用進(jìn)行觀察和分析，我們得到數(shù)據(jù)并行應(yīng)用的特點(diǎn)，即數(shù)據(jù)并行應(yīng)用的運(yùn)行過(guò)程具有階段性，并且每個(gè)數(shù)據(jù)并行應(yīng)用的作業(yè)可以劃分為多個(gè)階段執(zhí)行。在每個(gè)階段中會(huì)運(yùn)行多個(gè)獨(dú)立的任務(wù)，而任務(wù)的數(shù)目和數(shù)據(jù)分區(qū)的數(shù)目相同，每個(gè)任務(wù)會(huì)計(jì)算一個(gè)分區(qū)的數(shù)據(jù)，且每個(gè)任務(wù)對(duì)分區(qū)中的數(shù)據(jù)進(jìn)行同樣的操作。根據(jù)這個(gè)特點(diǎn)，文獻(xiàn)[2]提出了基于階段劃分的程序分析(Stage-Divided Program Analysis)，稱(chēng)之為SDPA，來(lái)簡(jiǎn)化和加速數(shù)據(jù)并行應(yīng)用的程序分析[2]。對(duì)于每個(gè)階段，我們對(duì)其重新劃分為一個(gè)或多個(gè)運(yùn)行周期。對(duì)于每個(gè)周期內(nèi)的用戶(hù)定義函數(shù)，將其抽取出來(lái)并融合為一個(gè)方便分析的函數(shù)。這樣避免了過(guò)程間分析且規(guī)避開(kāi)不必要分析的復(fù)雜數(shù)據(jù)處理系統(tǒng)框架代碼。

2.1.1 問(wèn)題分析及解決思路

性能對(duì)于數(shù)據(jù)并行應(yīng)用程序至關(guān)重要，而通過(guò)優(yōu)化代碼來(lái)提高應(yīng)用程序的性能是一種好方法。程序分析是一種常用的方法，它分析程序的行為，并獲得程序的正確性，安全性和活躍性等屬性來(lái)優(yōu)化程序。這些大數(shù)據(jù)處理系統(tǒng)的編程接口支持?jǐn)?shù)據(jù)并行運(yùn)算符，使得編寫(xiě)大數(shù)據(jù)應(yīng)用程序變得很容易，且只需要少量代碼就能完成編寫(xiě)工作。但是，這些應(yīng)用程序的每個(gè)運(yùn)算符都會(huì)調(diào)用大量的框架代碼。因此一個(gè)簡(jiǎn)短的應(yīng)用程序可能會(huì)引用很多類(lèi)和方法，并且分析這些并行數(shù)據(jù)應(yīng)用程序會(huì)花費(fèi)大量時(shí)間。

2.1.2 SDPA的設(shè)計(jì)與實(shí)現(xiàn)

數(shù)據(jù)并行應(yīng)用有一個(gè)特點(diǎn)，就是在運(yùn)行階段會(huì)被劃分為多個(gè)Stage，而每個(gè)Stage的任務(wù)相對(duì)獨(dú)立，即所有的任務(wù)都對(duì)不同的數(shù)據(jù)分區(qū)進(jìn)行相同的計(jì)算并且具有相同的shuffle依賴(lài)?；谶@些發(fā)現(xiàn)，文獻(xiàn)[2]提出了SDPA來(lái)簡(jiǎn)化加速數(shù)據(jù)并行應(yīng)用的程序分析。SDPA的處理流程如圖1所示。

圖1 SDPA處理流程圖Fig.1 Flow chart of SDPA

圖2 帶有Cache的Phase劃分Fig.2 Phase partition with Cache

（1）Phase劃分

在Spark中，每個(gè)Job可以劃分為一個(gè)或多個(gè)Phase。每個(gè)Phase可以分為三個(gè)部分：從數(shù)據(jù)源讀取數(shù)據(jù)對(duì)象，例如緩存RDD (Resilient Distributed Datasets) 或Shuffle緩沖區(qū)；對(duì)每個(gè)數(shù)據(jù)對(duì)象執(zhí)行一系列的用戶(hù)自定義函數(shù)進(jìn)行計(jì)算；計(jì)算結(jié)果寫(xiě)入新的數(shù)據(jù)收集器。Phase的劃分如圖2所示，按照Phase的定義，Phase與Spark劃分的Stage區(qū)別在于，Stage中間可能有緩存操作，緩存操作會(huì)對(duì)Stage進(jìn)行隔斷，因此一個(gè)Stage會(huì)被劃分為一個(gè)或多個(gè)Phase。

（2）用戶(hù)自定義函數(shù)融合

每個(gè)Phase，都是對(duì)數(shù)據(jù)源中的數(shù)據(jù)對(duì)象應(yīng)用一系列用戶(hù)定義函數(shù)的過(guò)程。因此，將每個(gè)Phase中各個(gè)算子的用戶(hù)定義函數(shù)抽取出來(lái)，然后將這些函數(shù)融合成為一個(gè)大的函數(shù)，可以將這些核心的函數(shù)變成一個(gè)函數(shù)。這樣可以跳出算子的束縛，可以更加容易的分析一系列的算子代碼。Phase中對(duì)象的操作如圖3所示。

融合過(guò)程使用融合工具Soot來(lái)實(shí)現(xiàn)，然后操作Soot生成的中間語(yǔ)言Jimple代碼。對(duì)每個(gè)Phase的迭代融合機(jī)制可概括為以下四個(gè)步驟：

● 獲取當(dāng)前Phase的最后一個(gè)RDD

● 獲得完整的RDD鏈

● 通過(guò)Java的反射機(jī)制抽取出每個(gè)RDD的UDF

● 將每個(gè)UDF的輸入輸出相連接

融合過(guò)程中，需要針對(duì)每個(gè)算子的語(yǔ)義進(jìn)行處理。將一個(gè)UDF的輸出作為接下來(lái)相鄰UDF的輸入，這樣就可以將一系列的UDF融合成為一個(gè)大的函數(shù)，然后使用Soot聲明一個(gè)類(lèi)，將生成的循環(huán)放入這個(gè)類(lèi)中。在后面的程序分析過(guò)程中，就可以直接分析這個(gè)融合生成的類(lèi)。

圖3 Phase中對(duì)象操作示意圖Fig.3 A sketch for data object operation in Phase

（3）代碼處理與分析

在SDPA中，我們使用Soot-SPARK來(lái)對(duì)融合之后的代碼進(jìn)行程序分析。Soot-SPARK是一個(gè)用Java實(shí)現(xiàn)指針?lè)治龅目蚣?，它支持基于子集的和基于等價(jià)的分析以及兩者之間的任何分析。SPARK是作為Soot框架的一部分提供的，可以在soot.jimple.spark.*包中找到。SPARK的一部分提供指針?lè)治觯⑶铱梢允褂眠x項(xiàng)來(lái)控制分析的多個(gè)方面。由于使用Soot-SPARK分析代碼需要一個(gè)主類(lèi)與入口方法，而在對(duì)用戶(hù)定義函數(shù)進(jìn)行融合之后只是得到一個(gè)大的函數(shù)，因此需要對(duì)融合之后的函數(shù)進(jìn)行處理。SDPA將融合之后的函數(shù)放到一個(gè)Phase-Function-Class里面，然后添加入口的apply方法，然后將這個(gè)類(lèi)和前面的Phase-Function-Class鏈接起來(lái)。這就可以使用Soot-SPARK進(jìn)行程序分析。

（4）閉包處理與分析過(guò)程加速

在SDPA中，閉包處理通過(guò)以Soot對(duì)Jimple代碼分析為基礎(chǔ)。針對(duì)不同的RDD，每個(gè)RDD都會(huì)對(duì)應(yīng)一個(gè)算子，對(duì)每個(gè)算子來(lái)說(shuō)，它生成的RDD都是固定類(lèi)型的，譬如Map算子，生成的是MapParitionRDD。因此，對(duì)于這些RDD，首先進(jìn)行強(qiáng)制類(lèi)型轉(zhuǎn)換，得到精確類(lèi)型的RDD。得到精確類(lèi)型之后，通過(guò)觀察Jimple代碼，遍歷其字段，通過(guò)判斷字段的name是否包含“$outer”來(lái)判斷這些是否是閉包變量。針對(duì)這些閉包變量，使用Soot將其注入到最后融合的Phase-Function-Class中。

此外，在完成迭代器融合之后需要對(duì)融合生成的Phase-Function-Class進(jìn)行程序分析。首先需要對(duì)Phase-Function-Class需要的類(lèi)和方法進(jìn)行加載，而Soot-SPARK的加載方式是全量加載，也就是說(shuō)會(huì)加載很多不必要的方法，因此為了加快分析過(guò)程，SDPA實(shí)現(xiàn)了增量加載。針對(duì)迭代應(yīng)用，SDPA實(shí)現(xiàn)了cache code，以方便復(fù)用分析結(jié)果。

2.2 海量存儲(chǔ)系統(tǒng)中的軟件定義QoS機(jī)制技術(shù)

隨著數(shù)據(jù)信息的快速發(fā)展，對(duì)大容量存儲(chǔ)系統(tǒng)的需求日益增長(zhǎng)，海量存儲(chǔ)系統(tǒng)逐漸成為研究熱點(diǎn)。海量存儲(chǔ)系統(tǒng)由客戶(hù)端、管理節(jié)點(diǎn)、存儲(chǔ)節(jié)點(diǎn)等三種節(jié)點(diǎn)組成，結(jié)構(gòu)圖如圖4所示。管理節(jié)點(diǎn)存儲(chǔ)命名空間和系統(tǒng)的元數(shù)據(jù)，如文件名、其對(duì)應(yīng)的對(duì)象號(hào)、以及該對(duì)象保存在哪個(gè)數(shù)據(jù)節(jié)點(diǎn)上等信息；數(shù)據(jù)節(jié)點(diǎn)保存文件數(shù)據(jù)（對(duì)象），對(duì)象以對(duì)象號(hào)標(biāo)識(shí)應(yīng)用服務(wù)器通過(guò)定制協(xié)議或 HTTP 訪(fǎng)問(wèn)存儲(chǔ)系統(tǒng)。海量存儲(chǔ)系統(tǒng)的核心是分布式文件系統(tǒng)，文件系統(tǒng)允許從一個(gè)計(jì)算機(jī)網(wǎng)絡(luò)中的多臺(tái)主機(jī)上訪(fǎng)問(wèn)文件，這使得多個(gè)用戶(hù)可以通過(guò)多臺(tái)主機(jī)共享文件及存儲(chǔ)資源。

圖4 海量存儲(chǔ)系統(tǒng)Fig.4 Mass storage system

海量存儲(chǔ)系統(tǒng)的發(fā)展也使得應(yīng)用越來(lái)越傾向于數(shù)據(jù)密集型，導(dǎo)致高度密集的海量數(shù)據(jù)I/O吞吐需求日益增長(zhǎng)。同時(shí)半導(dǎo)體技術(shù)的飛速發(fā)展，使得固態(tài)硬盤(pán)（Solid State Drives）得到迅速普及和廣泛應(yīng)用。但是盡管新的高速存儲(chǔ)設(shè)備的出現(xiàn)和部署使得HPC系統(tǒng)的整體I/O性能穩(wěn)步提高，但是相比于計(jì)算性能的增長(zhǎng)，I/O資源仍處于不足的狀態(tài)。這使得多應(yīng)用之間對(duì)于存儲(chǔ)資源的競(jìng)爭(zhēng)和干擾極大程度上影響應(yīng)用的性能，譬如一個(gè)規(guī)模龐大的作業(yè)因?yàn)榈却徛腎/O而被阻塞，又或者一個(gè)小的作業(yè)在運(yùn)行時(shí)產(chǎn)生了大量I/O阻塞了其他優(yōu)先級(jí)較高的應(yīng)用。因此可以得出I/O的分配不合理不僅是存儲(chǔ)資源的低利用率，也是對(duì)計(jì)算資源的浪費(fèi)。所以，使得每個(gè)應(yīng)用占據(jù)與它的計(jì)算資源匹配的I/O帶寬對(duì)于HPC存儲(chǔ)系統(tǒng)來(lái)說(shuō)很有必要。

2.2.1 問(wèn)題分析及解決思路

在HPC平臺(tái)上實(shí)現(xiàn)I/O控制面臨很多挑戰(zhàn)：第一，HPC應(yīng)用可以輕易達(dá)到上千的計(jì)算節(jié)點(diǎn)的規(guī)模，每秒產(chǎn)生百萬(wàn)級(jí)別的I/O請(qǐng)求。這使得全局上監(jiān)控應(yīng)用的I/O行為十分困難。同時(shí)搜集到應(yīng)用所有線(xiàn)程的I/O行為會(huì)造成監(jiān)測(cè)規(guī)模過(guò)于龐大的問(wèn)題。第二，I/O請(qǐng)求具有突發(fā)性并且在不同服務(wù)器上分配不均。這些特性要求I/O控制做到細(xì)粒度（應(yīng)對(duì)I/O突發(fā)性）和全局優(yōu)化（應(yīng)對(duì)I/O分配不均）。在這兩點(diǎn)上實(shí)現(xiàn)具有較大難度，同時(shí)還要求服務(wù)器去學(xué)習(xí)應(yīng)用的I/O變化規(guī)律也十分困難。第三，保障應(yīng)用的帶寬并不是簡(jiǎn)單的設(shè)置一個(gè)硬性的標(biāo)準(zhǔn)，同時(shí)需要使得整個(gè)系統(tǒng)的I/O性能達(dá)到最優(yōu)，例如，當(dāng)應(yīng)用的帶寬被自身的訪(fǎng)問(wèn)模式所限制無(wú)法達(dá)到理想帶寬時(shí)，余下的帶寬就應(yīng)當(dāng)分配給其他應(yīng)用使用以達(dá)到整體性能最優(yōu)。

為此，文獻(xiàn)[7]提出了一個(gè)通用的I/O帶寬控制方案，基于OrangeFs并行文件系統(tǒng)實(shí)現(xiàn)，其核心思想是在HPC存儲(chǔ)系統(tǒng)中加入Data Plane和Control Plane組件去控制應(yīng)用的I/O行為，同時(shí)使用令牌桶技術(shù)達(dá)到多應(yīng)用間的公平性和整體性能最優(yōu)，架構(gòu)如圖5所示[7]。

2.2.2 SDQoS設(shè)計(jì)與實(shí)現(xiàn)

(1) 數(shù)據(jù)模塊和控制模塊

每一個(gè)服務(wù)端維持一個(gè)Data Plane，是監(jiān)測(cè)和控制應(yīng)用I/O行為的核心組件，同時(shí)這一系列操作會(huì)在實(shí)際I/O行為發(fā)生之前進(jìn)行處理。該組件的實(shí)現(xiàn)在不同的文件系統(tǒng)上會(huì)有不同的實(shí)現(xiàn)方式，例如在lustre文件系統(tǒng)上，Data Plane可以實(shí)現(xiàn)在OST層，在pvfs文件系統(tǒng)中，文獻(xiàn)[7]實(shí)現(xiàn)在服務(wù)端。

Data Plane首先與Control Plane進(jìn)行連接，獲取到應(yīng)用的I/O需求，并為每個(gè)應(yīng)用維護(hù)一個(gè)單獨(dú)的隊(duì)列。然后，每個(gè)到來(lái)的I/O請(qǐng)求從令牌桶中獲得令牌，根據(jù)獲得令牌的情況被服務(wù)。

Control Plane在整個(gè)系統(tǒng)運(yùn)行過(guò)程中是全局且唯一的，它并不是單獨(dú)運(yùn)行在某個(gè)節(jié)點(diǎn)上，而是邏輯上存在的一個(gè)分布式調(diào)度組件，用于接收應(yīng)用的特性并基于這些特性計(jì)算出應(yīng)用應(yīng)該被分配的帶寬（也可以直接指定帶寬）。需要指出的是，這些被計(jì)算出的帶寬并不是應(yīng)用強(qiáng)制需要達(dá)到的帶寬。由于實(shí)際I/O過(guò)程的不均衡以及服務(wù)器能提供帶寬的物理限制，應(yīng)用實(shí)際得到的帶寬也會(huì)進(jìn)行調(diào)整。

圖5 SDQoS框架Fig.5 .SDQoS framework

(2) 本地I/O控制

在SDQoS中，文獻(xiàn)[7]利用令牌桶去限制單個(gè)應(yīng)用的I/O帶寬。

令牌桶策略在網(wǎng)絡(luò)中被廣泛用于管理和整形網(wǎng)絡(luò)數(shù)據(jù)包，它能夠應(yīng)對(duì)突發(fā)流量同時(shí)保障了常規(guī)流量。因?yàn)樵贖PC中，I/O同樣存在突發(fā)現(xiàn)象，所以該令牌桶策略在HPC環(huán)境下的I/O場(chǎng)景中同樣適用。

令牌桶策略在HPC中的使用和在網(wǎng)絡(luò)應(yīng)用中的使用有很大的區(qū)別。在網(wǎng)絡(luò)中，超出限制的數(shù)據(jù)包可以被丟棄重發(fā)，而在HPC中，I/O不可以被丟棄，需要被緩存起來(lái)，這樣就會(huì)造成延遲和阻塞。并且，有時(shí)需要允許應(yīng)用得到超過(guò)它得到的令牌數(shù)的I/O資源以達(dá)到整個(gè)系統(tǒng)I/O性能最優(yōu)。

在具體實(shí)現(xiàn)上，我們?yōu)槊總€(gè)應(yīng)用都分配了單獨(dú)的令牌桶。令牌桶根據(jù)應(yīng)用的需求設(shè)定令牌產(chǎn)生速率以及令牌桶容量。其中，令牌產(chǎn)生速率代表了應(yīng)用穩(wěn)定情況下的帶寬，令牌桶容量代表了應(yīng)用在突發(fā)情況下所能分配的最大帶寬。

3 RDF圖數(shù)據(jù)的查詢(xún)與匹配

由于圖數(shù)據(jù)模型具有描述能力強(qiáng)，適用范圍廣等優(yōu)點(diǎn)，越來(lái)越多的數(shù)據(jù)使用圖數(shù)據(jù)模型發(fā)布或存儲(chǔ)[8-10]。資源描述框架（Resource Description Framework，RDF）數(shù)據(jù)是圖數(shù)據(jù)中的一種。由于RDF數(shù)據(jù)模型有著諸多優(yōu)點(diǎn)，譬如方便簡(jiǎn)潔，模塊化程度高等，越來(lái)越多的機(jī)構(gòu)或組織加入了RDF用戶(hù)社區(qū)。

SPARQL語(yǔ)言是一種常用的圖查詢(xún)語(yǔ)言。SPARQL查詢(xún)語(yǔ)句通常構(gòu)成一個(gè)查詢(xún)圖，表示在對(duì)應(yīng)RDF圖數(shù)據(jù)上的子圖匹配查詢(xún)。SPARQL是知識(shí)圖的固有訪(fǎng)問(wèn)接口，但復(fù)雜難懂，文獻(xiàn)[3]提出以自然語(yǔ)言為訪(fǎng)問(wèn)接口，設(shè)計(jì)了基于異構(gòu)圖模式近似匹配方法的自然語(yǔ)言問(wèn)答系統(tǒng)。此外，SPARQL查詢(xún)引擎無(wú)法在合理時(shí)間內(nèi)處理復(fù)雜查詢(xún)，文獻(xiàn)[4]提出了共享內(nèi)存環(huán)境下圖查詢(xún)并行處理系統(tǒng)ParTriple。

3.1 異構(gòu)圖模式近似匹配方法

3.1.1 研究問(wèn)題

隨著互聯(lián)網(wǎng)的飛速發(fā)展，大量的知識(shí)庫(kù)可供公眾訪(fǎng)問(wèn)，例如DBpedia，YAGO，F(xiàn)reebase。不同于傳統(tǒng)的信息檢索中使用的文檔庫(kù)，知識(shí)庫(kù)以RDF形式，即三元組（主語(yǔ)，謂語(yǔ)，賓語(yǔ)）的形式整合細(xì)粒度的信息，因此它在整合信息、加強(qiáng)智能搜索方面擔(dān)任著非常重要的角色[4]。

然而，由于知識(shí)庫(kù)采用普通用戶(hù)不熟悉的結(jié)構(gòu)化的方式來(lái)存儲(chǔ)信息，所以訪(fǎng)問(wèn)使用這些大規(guī)模知識(shí)庫(kù)中的信息成為當(dāng)前困擾普通用戶(hù)的問(wèn)題[11-12]。另外，因?yàn)橹R(shí)庫(kù)以圖的結(jié)構(gòu)來(lái)組織信息，所以，問(wèn)題的本質(zhì)也就是圖模式的近似匹配問(wèn)題。但是為了連接用戶(hù)和知識(shí)圖，需要有一個(gè)訪(fǎng)問(wèn)接口來(lái)方便用戶(hù)使用。

雖然知識(shí)圖提供了固有的訪(fǎng)問(wèn)接口，例如SPARQL，但是復(fù)雜的語(yǔ)法和知識(shí)圖結(jié)構(gòu)使得它不能直接為普通用戶(hù)所用。因此，為知識(shí)圖設(shè)計(jì)一個(gè)高效且方便用戶(hù)使用的訪(fǎng)問(wèn)接口成為人們亟待解決的問(wèn)題。由于以自然語(yǔ)言為訪(fǎng)問(wèn)接口，方便用戶(hù)直接從知識(shí)庫(kù)中獲取信息，所以文獻(xiàn)[3]提出了基于異構(gòu)圖模式近似匹配方法，并在此基礎(chǔ)上實(shí)現(xiàn)了自然語(yǔ)言問(wèn)答系統(tǒng)Svega[3]。

3.1.2 基于語(yǔ)義向量的圖模式匹配與相似度計(jì)算

給定一個(gè)查詢(xún)圖Q=（V,E,RE），其中V=v1,v2,…，vn，節(jié)點(diǎn)集合V中的每一個(gè)節(jié)點(diǎn)vi在知識(shí)庫(kù)中都有一個(gè)匹配的候選結(jié)合Svi，則當(dāng)且僅當(dāng)滿(mǎn)足以下兩個(gè)條件時(shí)，知識(shí)庫(kù)中的一個(gè)子圖sub-KG才是查詢(xún)圖Q的匹配子圖：

（1）對(duì)于查詢(xún)圖Q中的任何一個(gè)節(jié)點(diǎn)vi，一定有一個(gè)節(jié)點(diǎn)ui∈Svi，并且該節(jié)點(diǎn)被包含在子圖sub-KG中；

（2）如果查詢(xún)圖Q中的兩個(gè)節(jié)點(diǎn)vi和vj之間存在一條邊，則在子圖sub-KG中一定存在一條路徑P(ui,uj)，并且節(jié)點(diǎn)ui和uj分別是查詢(xún)圖中節(jié)點(diǎn)vi和vj對(duì)應(yīng)的匹配節(jié)點(diǎn)。

針對(duì)異構(gòu)圖模式近似匹配問(wèn)題，文獻(xiàn)[3]提出了一種以圖模式近似匹配技術(shù)來(lái)訪(fǎng)問(wèn)知識(shí)圖的方法。為了更加精準(zhǔn)的挖掘出查詢(xún)目的，文獻(xiàn)[3]提出了一種實(shí)體驅(qū)動(dòng)的策略來(lái)構(gòu)建查詢(xún)圖。首先基于查詢(xún)圖中節(jié)點(diǎn)特征識(shí)別出自然語(yǔ)言問(wèn)句中的實(shí)體，然后根據(jù)問(wèn)句中單詞之間的語(yǔ)法關(guān)系分析挖掘出實(shí)體之間的謂語(yǔ)關(guān)系，從而構(gòu)建出查詢(xún)圖。就圖模式匹配過(guò)程而言，其本質(zhì)就是消歧處理，所以該系統(tǒng)首先基于查詢(xún)圖的結(jié)構(gòu)特征進(jìn)行消歧，提出了基于節(jié)點(diǎn)匹配來(lái)從知識(shí)庫(kù)中得到查詢(xún)圖的異構(gòu)子圖，同時(shí)挖掘匹配的路徑，過(guò)濾歧義信息，然后基于查詢(xún)圖的語(yǔ)義特征進(jìn)行消歧，提出了合成詞向量的方法來(lái)表示查詢(xún)圖中邊和匹配子圖中路徑的語(yǔ)義信息，從而簡(jiǎn)化了相似度的計(jì)算，同時(shí)可以根據(jù)語(yǔ)義相似度來(lái)過(guò)濾歧義信息。

3.2 共享內(nèi)存環(huán)境下圖查詢(xún)并行處理系統(tǒng)ParTriple

3.2.1 研究問(wèn)題

隨著RDF數(shù)據(jù)的爆炸式增長(zhǎng)，現(xiàn)有的一些SPARQL查詢(xún)處理系統(tǒng)已無(wú)法在合理時(shí)間內(nèi)處理復(fù)雜查詢(xún)。為此，SPARQL查詢(xún)引擎應(yīng)當(dāng)使用并行處理技術(shù)來(lái)實(shí)現(xiàn)對(duì)復(fù)雜查詢(xún)的高效處理。然而，當(dāng)前的一些SPARQL查詢(xún)并行處理技術(shù)有著查詢(xún)優(yōu)化效率低下且生成的查詢(xún)計(jì)劃不利于并行，系統(tǒng)并行程度較低等不足。在這種背景下，將SPARQL圖查詢(xún)處理與并行技術(shù)相結(jié)合，開(kāi)發(fā)SPARQL圖查詢(xún)并行處理系統(tǒng)，即共享內(nèi)存環(huán)境下的圖查詢(xún)并行處理系統(tǒng)，顯得尤為必要。

開(kāi)發(fā)圖查詢(xún)并行處理系統(tǒng)主要有兩方面的挑戰(zhàn)。一方面，查詢(xún)優(yōu)化對(duì)查詢(xún)處理的性能有很大影響，其生成的查詢(xún)計(jì)劃不可避免地影響查詢(xún)執(zhí)行的并行處理。另一方面，由于現(xiàn)代計(jì)算機(jī)上配備的處理核心數(shù)目越來(lái)越多，如何在單機(jī)上最大限度地利用這些計(jì)算能力來(lái)進(jìn)行SPARQL查詢(xún)處理本身也有很多難點(diǎn)，譬如并行性開(kāi)發(fā)不夠，資源競(jìng)爭(zhēng)過(guò)多等等。為了應(yīng)對(duì)這些挑戰(zhàn)，文獻(xiàn)[4]在高可擴(kuò)展的RDF數(shù)據(jù)存儲(chǔ)查詢(xún)系統(tǒng)TripleBit的基礎(chǔ)上設(shè)計(jì)并實(shí)現(xiàn)了ParTriple 系統(tǒng)[4]。

3.2.2 并行處理系統(tǒng)ParTriple

ParTriple旨在為多核計(jì)算機(jī)環(huán)境下的SPARQL圖查詢(xún)提供并行處理。文獻(xiàn)[3]提出了一種基于自底向上樹(shù)的查詢(xún)計(jì)劃生成方法。另一方面，文獻(xiàn)[4]提出了一種兩級(jí)并行模型來(lái)執(zhí)行查詢(xún)計(jì)劃，以充分利用多核架構(gòu)的計(jì)算能力，提高查詢(xún)處理性能。

ParTriple系統(tǒng)主要由數(shù)據(jù)導(dǎo)入模塊、數(shù)據(jù)結(jié)構(gòu)模塊、查詢(xún)處理模塊三部分組成。ParTriple通過(guò)數(shù)據(jù)導(dǎo)入模塊，對(duì)RDF數(shù)據(jù)進(jìn)行解析、字典映射，并進(jìn)行排序。在此期間，數(shù)據(jù)結(jié)構(gòu)模塊與數(shù)據(jù)導(dǎo)入模塊進(jìn)行交互，建立數(shù)據(jù)字典，存儲(chǔ)三元組數(shù)據(jù)，并建立相應(yīng)的索引。查詢(xún)處理模塊用于處理用戶(hù)提交的SPARQL查詢(xún)語(yǔ)句?？煞殖蒘PARQL語(yǔ)句解析、查詢(xún)優(yōu)化器、任務(wù)管理、并行操作符等子模塊。

首先，該系統(tǒng)提出了一種高效、易于并行的查詢(xún)計(jì)劃生成算法。這種算法生成的查詢(xún)計(jì)劃可以使用流水線(xiàn)處理技術(shù)，且不同的流水線(xiàn)之間不需要相互等待。進(jìn)一步地，這種查詢(xún)計(jì)劃可以更有效地削減中間結(jié)果，提高查詢(xún)處理性能。接著，我們提出了一種數(shù)據(jù)塊級(jí)與模式級(jí)的兩級(jí)并行執(zhí)行框架，將查詢(xún)執(zhí)行分解成基于數(shù)據(jù)存儲(chǔ)分塊的子任務(wù)與基于中間結(jié)果分塊的子任務(wù)，從操作符間并行與操作符內(nèi)并行兩個(gè)層面開(kāi)發(fā)了系統(tǒng)的并行性。最后，我們開(kāi)發(fā)了三種不同的并行操作符，分別針對(duì)數(shù)據(jù)掃描，連接處理，數(shù)據(jù)洗牌等操作，進(jìn)一步提升了系統(tǒng)查詢(xún)處理的性能。

4 大數(shù)據(jù)分析技術(shù)

隨著信息技術(shù)的迅猛發(fā)展，越來(lái)越多的應(yīng)用會(huì)產(chǎn)生海量的數(shù)據(jù)集。這些應(yīng)用需要對(duì)大數(shù)據(jù)進(jìn)行快速計(jì)算、分析與處理，給大數(shù)據(jù)計(jì)算理論框架帶來(lái)了高吞吐、低延時(shí)、高可擴(kuò)展、高容錯(cuò)等迫切需求。近年來(lái)，以Hadoop、Spark和Storm為代表的大數(shù)據(jù)計(jì)算理論框架受到業(yè)界的廣泛關(guān)注并投入使用。

Hadoop是一種專(zhuān)用于批處理的計(jì)算框架，適用于需要分析海量的離線(xiàn)數(shù)據(jù)集的應(yīng)用場(chǎng)景。Hadoop實(shí)現(xiàn)了MapReduce的思想，通過(guò)數(shù)據(jù)切片計(jì)算來(lái)處理海量的離線(xiàn)數(shù)據(jù)集，具有高可擴(kuò)展性。由于Hadoop需要將所有中間輸出和結(jié)果持久化到磁盤(pán)，頻繁的磁盤(pán)IO操作會(huì)影響計(jì)算的速度。Spark是一種基于內(nèi)存計(jì)算的批處理計(jì)算框架，適用于需要反復(fù)操作特定數(shù)據(jù)集的應(yīng)用場(chǎng)景。Spark通過(guò)RDD（Resilient Distributed Dataset，彈性分布式數(shù)據(jù)集）將計(jì)算的中間輸出和結(jié)果存儲(chǔ)在內(nèi)存中，能夠顯著加速Hadoop作業(yè)的執(zhí)行速度。Storm是一種專(zhuān)用于流處理的計(jì)算框架，適用于需要對(duì)海量連續(xù)流數(shù)據(jù)進(jìn)行實(shí)時(shí)處理的應(yīng)用場(chǎng)景。Storm通過(guò)將應(yīng)用抽象成DAG（Directed Acyclic Graph，有向無(wú)環(huán)圖），并利用分布式RPC（Remote Procedure Call，遠(yuǎn)程過(guò)程調(diào)用）框架來(lái)支撐無(wú)邊界流數(shù)據(jù)的實(shí)時(shí)處理，具有非常低的延時(shí)。由于DAG中上下流任務(wù)的依賴(lài)關(guān)系會(huì)導(dǎo)致在任務(wù)恢復(fù)期間發(fā)生任務(wù)級(jí)聯(lián)等待的現(xiàn)象，影響處理性能，文獻(xiàn)[5]通過(guò)挖掘上下流任務(wù)的依賴(lài)關(guān)系，設(shè)計(jì)了一個(gè)低延時(shí)和高容錯(cuò)的分布式流處理系統(tǒng)。

4.1 分布式流處理容錯(cuò)系統(tǒng)Ares

為了滿(mǎn)足實(shí)時(shí)流處理應(yīng)用的低延遲和高容錯(cuò)的需求，分布式流處理系統(tǒng)需要保障系統(tǒng)能夠以低延遲的方式處理海量的實(shí)時(shí)數(shù)據(jù)流，同時(shí)當(dāng)系統(tǒng)中的節(jié)點(diǎn)發(fā)生故障時(shí)，系統(tǒng)能夠在較短的時(shí)間內(nèi)恢復(fù)正常?，F(xiàn)有的分布式流處理系統(tǒng)通常通過(guò)優(yōu)化任務(wù)調(diào)度來(lái)實(shí)現(xiàn)海量實(shí)時(shí)數(shù)據(jù)流的低延遲處理。典型的分布式流處理系統(tǒng)任務(wù)調(diào)度策略通過(guò)將流處理應(yīng)用拓?fù)渲械纳舷铝魅蝿?wù)進(jìn)行綁定并分配到同一節(jié)點(diǎn)的方式，降低上下流任務(wù)之間的數(shù)據(jù)傳輸時(shí)間，從而保障低延遲處理性能[13-15]。然而，該任務(wù)調(diào)度策略忽視了上下流任務(wù)之間的依賴(lài)關(guān)系對(duì)系統(tǒng)容錯(cuò)性能的影響。即當(dāng)系統(tǒng)中的節(jié)點(diǎn)發(fā)生故障時(shí)，由于失效節(jié)點(diǎn)上存在大量的上下流任務(wù)，這些任務(wù)之間的依賴(lài)關(guān)系會(huì)導(dǎo)致在任務(wù)恢復(fù)期間發(fā)生任務(wù)級(jí)聯(lián)等待的現(xiàn)象，從而使得系統(tǒng)無(wú)法在較短的時(shí)間內(nèi)恢復(fù)正常[16-17]。

圖6 Ares系統(tǒng)架構(gòu)Fig.6 Ares framework

該研究指出實(shí)現(xiàn)一個(gè)低延遲和高容錯(cuò)的分布式流處理系統(tǒng)的關(guān)鍵在于能否在任務(wù)調(diào)度過(guò)程中充分挖掘流處理應(yīng)用拓?fù)渲猩舷铝魅蝿?wù)之間的依賴(lài)關(guān)系。為此，文獻(xiàn)[5]研發(fā)了分布式流處理容錯(cuò)系統(tǒng)Ares[5]。Ares在系統(tǒng)任務(wù)調(diào)度過(guò)程中兼顧上下流任務(wù)之間的依賴(lài)關(guān)系對(duì)處理性能和容錯(cuò)性能兩者的影響，并提出了一種容錯(cuò)調(diào)度問(wèn)題來(lái)同時(shí)優(yōu)化處理延遲和恢復(fù)時(shí)間。為了最大化系統(tǒng)效用，Ares利用單一任務(wù)的最佳放置策略往往取決于該任務(wù)的上下流任務(wù)的放置策略的特性，設(shè)計(jì)了一種基于最佳應(yīng)對(duì)動(dòng)態(tài)算法Nirvana來(lái)自動(dòng)優(yōu)化任務(wù)放置策略。相對(duì)于目前最新流處理系統(tǒng)，Ares將系統(tǒng)總體吞吐率提高了3.6倍，將平均處理延遲降低了50.2%，將平均恢復(fù)時(shí)間降低了52.5%。

圖6顯示了Ares的系統(tǒng)架構(gòu)。Ares的架構(gòu)在傳統(tǒng)分布式流處理系統(tǒng)架構(gòu)的基礎(chǔ)上，增加了一個(gè)負(fù)載監(jiān)視器和一個(gè)Nirvana控制器。負(fù)載監(jiān)視器負(fù)責(zé)實(shí)時(shí)監(jiān)控所有計(jì)算節(jié)點(diǎn)上的任務(wù)的資源使用情況。Nirvana控制器根據(jù)當(dāng)前系統(tǒng)的資源使用情況，通過(guò)Nirvana算法計(jì)算得到滿(mǎn)足低延遲和高容錯(cuò)需求的最佳任務(wù)調(diào)度方案。

4.2 面向文檔過(guò)濾的語(yǔ)言模型平滑方法

豐富的網(wǎng)絡(luò)資源中蘊(yùn)含著海量的數(shù)據(jù)信息，幫助用戶(hù)從中快速、準(zhǔn)確的找到所需的信息是一項(xiàng)極具價(jià)值的任務(wù)。但是海量的數(shù)據(jù)規(guī)模以及自然語(yǔ)言表達(dá)帶來(lái)的語(yǔ)義歧義性和多樣性，給信息系檢索帶來(lái)了巨大的挑戰(zhàn)。文獻(xiàn)[6]以實(shí)體為橋梁，以維基百科中的實(shí)體信息為內(nèi)容，提出了符合文檔語(yǔ)義主題下單詞概率分布的實(shí)體語(yǔ)義語(yǔ)言模型，并且提出兩層次的平滑方法，結(jié)合文檔無(wú)關(guān)的全局語(yǔ)料庫(kù)信息源和文檔主題相關(guān)的實(shí)體語(yǔ)義語(yǔ)言模型信息源來(lái)對(duì)原始文檔語(yǔ)言模型進(jìn)行平滑，使得平滑后的語(yǔ)言模型能夠很好的衡量查詢(xún)語(yǔ)句和文檔之間的語(yǔ)義相關(guān)性，提高了檢索系統(tǒng)的性能。

4.2.1 實(shí)體語(yǔ)義語(yǔ)言模型的構(gòu)造

文檔中的實(shí)體被鏈接到維基百科中。但是由于實(shí)體鏈接工具不是完美的，存在錯(cuò)誤的可能，不能保證百分百的正確率。為了處理這種不確定性，文獻(xiàn)[6]提出了硬合并（Hard-Fused Method）和軟合并（Soft-Fused Method）兩種方法。硬合并方法只考慮文檔中置信度比較高的實(shí)體，同時(shí)忽略實(shí)體的頻率信息。軟合并方法將置信度作為實(shí)體的權(quán)重，同時(shí)考慮實(shí)體的頻率信息。

硬合并方法僅考慮鏈接置信度大于特定閾值的實(shí)體，并且忽略實(shí)體在文檔中出現(xiàn)的次數(shù)。實(shí)體鏈接工具的精度有限，不可避免的會(huì)產(chǎn)生錯(cuò)誤。直接忽略低置信度的實(shí)體可以預(yù)防引入實(shí)體鏈接工具的錯(cuò)誤，只使用那些質(zhì)量高的、信得過(guò)的鏈接實(shí)體可以提高模型的健壯性。硬合并方法同時(shí)將所有高置信度的實(shí)體當(dāng)作一樣來(lái)對(duì)待，分配同樣的權(quán)重，即忽略它們?cè)谖臋n中的頻率信息。

另外一種構(gòu)建實(shí)體語(yǔ)義語(yǔ)言模型的方法是軟合并方法，這種方法考慮實(shí)體鏈接結(jié)果中的置信度等級(jí)和實(shí)體在文檔中頻率信息。文檔中實(shí)體的重要程度是不一樣的。重要實(shí)體的知識(shí)庫(kù)信息與文檔的語(yǔ)義主題更加相關(guān)。用SF-ESLM (Soft Fused-Entity Semantic Language Model)來(lái)表示軟合并方法生成的實(shí)體語(yǔ)義語(yǔ)言模型：

其中PSF-ESLM(w|d)表示單詞w在文檔d軟合并方法得到實(shí)體語(yǔ)義語(yǔ)言模型中的概率大小，M(d)表示文檔d中所有實(shí)體提及名字組成的集合。

4.2.2 兩層次的平滑方法

基于實(shí)體的語(yǔ)言模型平滑框架從文檔語(yǔ)義主題的角度出發(fā)，利用實(shí)體作為橋梁，構(gòu)建實(shí)體語(yǔ)義語(yǔ)言模型。在這個(gè)方法中，文檔中的實(shí)體被實(shí)體鏈接工具鏈接到外部實(shí)體知識(shí)庫(kù)中，如維基百科，然后使用軟合并方法和硬合并方法將實(shí)體在知識(shí)庫(kù)中的信息合并在一起組成實(shí)體語(yǔ)義語(yǔ)言模型。文獻(xiàn)[6]最后提出了兩層次的平滑方法，將上述語(yǔ)言模型結(jié)合在一起，可以很好的區(qū)分單詞與文檔主題的相關(guān)性。

圖7 基于實(shí)體的語(yǔ)義平滑方法示意圖Fig.7 A sketch for entity-based language model smoothing.

如圖7，整個(gè)框架包含原始文檔語(yǔ)言模型、實(shí)體語(yǔ)義語(yǔ)言模型和語(yǔ)料庫(kù)語(yǔ)言模型三個(gè)語(yǔ)言模型。原始文檔語(yǔ)言模型通過(guò)統(tǒng)計(jì)原始文檔中詞頻信息來(lái)計(jì)算得到。實(shí)體語(yǔ)義語(yǔ)言模型通過(guò)文檔中實(shí)體指向的維基百科主頁(yè)信息來(lái)計(jì)算得到。全局語(yǔ)料庫(kù)語(yǔ)言模型通過(guò)統(tǒng)計(jì)語(yǔ)料庫(kù)中的全局詞頻信息來(lái)計(jì)算得到。實(shí)體語(yǔ)義語(yǔ)言模型是整個(gè)框架的核心。它引入與文檔主題相關(guān)的語(yǔ)義信息，使得平滑后的語(yǔ)義模型更加接近文檔主題下的單詞概率分布。

5 總結(jié)與未來(lái)工作

本文簡(jiǎn)要介紹了大數(shù)據(jù)基礎(chǔ)理論以及大數(shù)據(jù)的存儲(chǔ)、檢索、分析和挖掘等關(guān)鍵技術(shù)，并介紹了低復(fù)雜度隱私保護(hù)數(shù)據(jù)聚合算法、面向數(shù)據(jù)并行的大數(shù)據(jù)處理技術(shù)、RDF圖數(shù)據(jù)查詢(xún)與匹配以及大數(shù)據(jù)分析技術(shù)等幾個(gè)方面的一些代表性工作。

未來(lái)，我們將在已有工作的基礎(chǔ)上繼續(xù)關(guān)注大數(shù)據(jù)基礎(chǔ)理論以及大數(shù)據(jù)系統(tǒng)的前沿技術(shù)發(fā)展趨勢(shì)。在大數(shù)據(jù)基礎(chǔ)理論方面，我們將在結(jié)合新型體系結(jié)構(gòu)的基礎(chǔ)上，進(jìn)一步研究大數(shù)據(jù)代數(shù)系統(tǒng)、數(shù)學(xué)結(jié)構(gòu)以及大數(shù)據(jù)度量指標(biāo)等方面的基礎(chǔ)科學(xué)問(wèn)題，從大數(shù)據(jù)的內(nèi)在結(jié)構(gòu)、本質(zhì)特征出發(fā)，為大數(shù)據(jù)的分析、計(jì)算提供基礎(chǔ)理論支撐。在大數(shù)據(jù)分析方面，我們將繼續(xù)探索大數(shù)據(jù)分析技術(shù)的一些共性問(wèn)題，例如新型數(shù)據(jù)挖掘算法、高維數(shù)據(jù)分析技術(shù)、基于深度學(xué)習(xí)的大數(shù)據(jù)處理技術(shù)以及多源異構(gòu)復(fù)雜數(shù)據(jù)的治理和分析技術(shù)。在大數(shù)據(jù)計(jì)算技術(shù)方面，我們將繼續(xù)關(guān)注新型體系結(jié)構(gòu)上的高能效大數(shù)據(jù)計(jì)算技術(shù)、以性能為導(dǎo)向的新型大數(shù)據(jù)計(jì)算框架，同時(shí)我們將在繼續(xù)關(guān)注大數(shù)據(jù)基礎(chǔ)理論與系統(tǒng)關(guān)鍵技術(shù)的基礎(chǔ)上，引入邊緣計(jì)算、霧計(jì)算等場(chǎng)景，研究物聯(lián)網(wǎng)環(huán)境下的大數(shù)據(jù)計(jì)算技術(shù)。最后，在研究大數(shù)據(jù)分析、計(jì)算等關(guān)鍵技術(shù)的同時(shí)，我們將在國(guó)家重點(diǎn)發(fā)展戰(zhàn)略的指導(dǎo)下，關(guān)注與國(guó)計(jì)民生息息相關(guān)重點(diǎn)大數(shù)據(jù)應(yīng)用系統(tǒng)，例如基于大數(shù)據(jù)挖掘的大健康分析系統(tǒng)、基于大數(shù)據(jù)處理的國(guó)防安全戰(zhàn)略防御系統(tǒng)等。

利益沖突聲明

所有作者聲明不存在利益沖突關(guān)系。