論文題目：PFPMine: A parallel approach for discovering interacting data entities in data-intensive cloud workflows

錄用時(shí)間：2020年7月7日

發(fā)表期刊：Future Generation Computer Systems（SCI檢索，JCR：Q1）

作者列表：

（1）黃昱澤，重慶交通大學(xué)，信息科學(xué)與工程學(xué)院，講師

（2）黃霽崴，中國(guó)石油大學(xué)（北京），信息科學(xué)與工程學(xué)院，教授

（3）劉   聰，山東理工大學(xué)，計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，教授

（4）張呈寧，新加坡Grab公司，數(shù)據(jù)工程師

DOI鏈接：https://doi.org/10.1016/j.future.2020.07.018

論文簡(jiǎn)介：

為了高效利用資源，需要將工作流部署于云環(huán)境之中。由于數(shù)據(jù)密集型工作流會(huì)對(duì)大量數(shù)據(jù)進(jìn)行操作，本文提出了一種基于頻繁模式的云工作流關(guān)聯(lián)數(shù)據(jù)發(fā)現(xiàn)和管理方法，并基于MapReduce框架對(duì)算法進(jìn)行并行化以提高效率。解決了在數(shù)據(jù)密集型工作流中發(fā)現(xiàn)關(guān)聯(lián)數(shù)據(jù)的問(wèn)題。通過(guò)使用真實(shí)數(shù)據(jù)集來(lái)評(píng)估該方法的效率，證明了我們的方法與傳統(tǒng)方法相比可以更高效的發(fā)現(xiàn)云工作流中的關(guān)聯(lián)數(shù)據(jù)。

背景與動(dòng)機(jī)：

云計(jì)算作為一種新興的計(jì)算模式能夠?qū)⒂?jì)算和存儲(chǔ)作為一種服務(wù)提供給用戶(hù)使用。云計(jì)算對(duì)資源的高效利用，可以顯著提高工作流的執(zhí)行效率。隨著云計(jì)算的廣泛應(yīng)用，為了高效利用資源，越來(lái)越多的公司或機(jī)構(gòu)將其工作流部署于云環(huán)境中，由于數(shù)據(jù)密集型工作流會(huì)對(duì)大量數(shù)據(jù)進(jìn)行操作，因此在將數(shù)據(jù)密集型工作流部署于云環(huán)境的過(guò)程中面臨著許多新的挑戰(zhàn)。

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

圖1FPMine總體框架

圖1介紹了一種基于頻繁模式的關(guān)聯(lián)數(shù)據(jù)發(fā)現(xiàn)方法的總體框架，該方法通過(guò)對(duì)工作流日志進(jìn)行分析，揭示出數(shù)據(jù)中的關(guān)聯(lián)關(guān)系，區(qū)分出數(shù)據(jù)間的重要程度。

頻繁模式挖掘算法的基礎(chǔ)是設(shè)定合適的支持度閾值。然而目前的頻繁模式挖掘算法大多采用人為設(shè)定的方法設(shè)定最小支持度閾值，顯然這存在明顯的問(wèn)題。雖然已經(jīng)有許多研究學(xué)者設(shè)計(jì)了一些自動(dòng)化設(shè)定最小支持度閾值的方法，但這些方法大多基于監(jiān)督學(xué)習(xí)或窮舉法，這將會(huì)導(dǎo)致算法的效率較為低下。為了解決這個(gè)問(wèn)題，本文提出了一種自動(dòng)化設(shè)定最小支持度閾值的方法，該方法基于數(shù)據(jù)項(xiàng)的統(tǒng)計(jì)分布特征，且不需要訓(xùn)練數(shù)據(jù)。設(shè)定最小支持度閾值的詳細(xì)步驟如算法１所述。

頻繁模式挖掘算法的基本思想是通過(guò)遍歷FP樹(shù)來(lái)查找頻繁項(xiàng)集。為了提高算法的執(zhí)行效率，本文重新設(shè)計(jì)了該算法用于查找頻繁二項(xiàng)集，設(shè)計(jì)了一種新的數(shù)據(jù)結(jié)構(gòu)，命名為FP矩陣。FP矩陣存儲(chǔ)了每對(duì)數(shù)據(jù)項(xiàng)的頻度信息及興趣度度量值。算法２為FP樹(shù)及FP矩陣構(gòu)造算法。FP樹(shù)及FP矩陣如圖２（ｂ）和（ｃ）所示。

圖2 FP樹(shù)及FP矩陣

構(gòu)建了FP樹(shù)和FP矩陣，下面將直接挖掘具有區(qū)分力的頻繁項(xiàng)集。與傳統(tǒng)的頻繁模式挖掘算法不同，本文提出一種直接挖掘具有區(qū)分力的頻繁二項(xiàng)集的算法，關(guān)注于挖掘頻繁二項(xiàng)集，而非頻繁模式，這將消耗更少的時(shí)間和資源。詳細(xì)的頻繁二項(xiàng)集挖掘算法如算法５所示。

為了應(yīng)對(duì)大規(guī)模數(shù)據(jù)集，本章提出了一種基于頻繁模式的并行化挖掘算法，并將其命名為PFPMine。該算法使用MapReduce框架將前面章節(jié)中提出的FPMine算法做并行化處理。圖３為相應(yīng)的PFPMine總體框架圖。

圖3 PFPMine總體框架圖

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

本文采用真實(shí)數(shù)據(jù)集對(duì)PFPMine算法進(jìn)行功能性評(píng)估。圖4（ａ）和圖4（ｂ）為采用PFPMine和FP-growth對(duì)三個(gè)不同的數(shù)據(jù)集進(jìn)行挖掘，并采用上述兩種不同的時(shí)延計(jì)算通信代價(jià)。結(jié)果表明采用PFPMine算法的通信代價(jià)明顯低于采用傳統(tǒng)的FP-growth算法所計(jì)算出的通信代價(jià)。

圖4通信代價(jià)

作者簡(jiǎn)介

黃霽崴博士，教授，博士生導(dǎo)師，石油數(shù)據(jù)挖掘北京市重點(diǎn)實(shí)驗(yàn)室主任，中國(guó)石油大學(xué)（北京）計(jì)算機(jī)科學(xué)與技術(shù)系主任。2015年度北京市優(yōu)秀人才，2018年度中國(guó)石油大學(xué)（北京）優(yōu)秀青年學(xué)者，2020年度北京市科技新星。分別在2009年和2014年于清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系獲得工學(xué)學(xué)士和工學(xué)博士學(xué)位，2012-2013年國(guó)家公派赴美國(guó)佐治亞理工學(xué)院聯(lián)合培養(yǎng)。研究方向包括：系統(tǒng)性能評(píng)價(jià)和優(yōu)化、隨機(jī)模型理論和應(yīng)用、服務(wù)質(zhì)量測(cè)量與保障技術(shù)、服務(wù)計(jì)算和物聯(lián)網(wǎng)等。擔(dān)任中國(guó)計(jì)算機(jī)學(xué)會(huì)（CCF）服務(wù)計(jì)算專(zhuān)委會(huì)委員，CCF高級(jí)會(huì)員，IEEE、ACM會(huì)員。已主持國(guó)家自然科學(xué)基金、北京市自然科學(xué)基金等科研項(xiàng)目13項(xiàng)，在國(guó)內(nèi)外著名期刊和會(huì)議發(fā)表論文五十余篇，出版學(xué)術(shù)專(zhuān)著1部，獲得國(guó)家發(fā)明專(zhuān)利5項(xiàng)、軟件著作權(quán)3項(xiàng)，擔(dān)任多個(gè)國(guó)際頂級(jí)期刊和知名會(huì)議審稿人。聯(lián)系郵箱：[email protected]。