本文關(guān)鍵詞：大規(guī)模動(dòng)態(tài)演化圖的存儲(chǔ)與分析系統(tǒng)研究

  更多相關(guān)文章： 動(dòng)態(tài)演化圖 平臺(tái)系統(tǒng) 圖分析 圖存儲(chǔ) 分布式系統(tǒng)

【摘要】：圖數(shù)據(jù)通過(guò)頂點(diǎn)和邊的結(jié)構(gòu)表達(dá)實(shí)體間的相互聯(lián)系。圖數(shù)據(jù)的分析計(jì)算技術(shù),也稱圖挖掘技術(shù),是通過(guò)分析實(shí)體間聯(lián)系,獲得關(guān)于實(shí)體的性質(zhì)、特征等重要信息的一項(xiàng)技術(shù),正廣泛地應(yīng)用于信息檢索、社交分析、生物計(jì)算等多個(gè)領(lǐng)域。本文所述的圖存儲(chǔ)分析系統(tǒng)是支持圖分析計(jì)算的平臺(tái)系統(tǒng)。它利用抽象的編程接口支持圖分析算法的高效實(shí)現(xiàn),利用優(yōu)化的系統(tǒng)設(shè)計(jì)提供高效的算法執(zhí)行,從而實(shí)現(xiàn)超大規(guī)模的圖數(shù)據(jù)分析。在大數(shù)據(jù)時(shí)代的今天,大規(guī)模圖存儲(chǔ)與分析系統(tǒng)及其相關(guān)技術(shù)已經(jīng)成為一個(gè)重要的研究方向。 而近年來(lái),隨著社交網(wǎng)絡(luò)媒體、移動(dòng)互聯(lián)網(wǎng)等新型應(yīng)用的普及,信息的組織方式、傳播方式等,正發(fā)生著新的變化——信息呈現(xiàn)出更為明顯的動(dòng)態(tài)化特征。隨著這一變化,捕捉了數(shù)據(jù)時(shí)序特征的動(dòng)態(tài)演化圖,其數(shù)據(jù)挖掘分析的價(jià)值正受到更多的重視,并隨著演化圖數(shù)據(jù)分析理論研究的同步深入,逐漸成為一個(gè)新的發(fā)展趨勢(shì)。然而現(xiàn)有的圖存儲(chǔ)與分析平臺(tái)系統(tǒng)針對(duì)的是靜態(tài)圖,并不適合動(dòng)態(tài)演化圖。因此,本文研究問(wèn)題的重點(diǎn),就在于：如何針對(duì)動(dòng)態(tài)演化圖分析這一類新的應(yīng)用,設(shè)計(jì)并實(shí)現(xiàn)高效的大規(guī)模存儲(chǔ)分析系統(tǒng)。 我們通過(guò)分析,將動(dòng)態(tài)演化圖相關(guān)的應(yīng)用主要總結(jié)為：(1)分析動(dòng)態(tài)演化圖準(zhǔn)實(shí)時(shí)狀態(tài)和(2)分析動(dòng)態(tài)演化圖長(zhǎng)期變化趨勢(shì)兩類。前者著重于分析動(dòng)態(tài)演化圖的最新?tīng)顟B(tài),而后者著重于分析動(dòng)態(tài)演化圖的長(zhǎng)期歷史變化過(guò)程。在文中,我們?yōu)檫@兩類應(yīng)用算法,設(shè)計(jì)并實(shí)現(xiàn)了動(dòng)態(tài)演化圖存儲(chǔ)、分析系統(tǒng)。該系統(tǒng)以圖數(shù)據(jù)的實(shí)時(shí)變化作為輸入,產(chǎn)生具有全局一致性的圖數(shù)據(jù)更新,并用于動(dòng)態(tài)演化圖準(zhǔn)實(shí)時(shí)狀態(tài)分析；同時(shí),它會(huì)將接收到的時(shí)序數(shù)據(jù)存儲(chǔ)下來(lái),重新組織并用于動(dòng)態(tài)演化圖長(zhǎng)期變化趨勢(shì)分析。在系統(tǒng)的設(shè)計(jì)實(shí)現(xiàn)中,我們將針對(duì)動(dòng)態(tài)演化圖準(zhǔn)實(shí)時(shí)狀態(tài)分析和動(dòng)態(tài)演化圖長(zhǎng)期變化趨勢(shì)分析的兩部分功能分別抽象成以下兩個(gè)子問(wèn)題加以解決： 一、動(dòng)態(tài)演化圖在線分析的系統(tǒng)問(wèn)題。在該問(wèn)題中,大量新的圖數(shù)據(jù)高速產(chǎn)生,應(yīng)用需要不斷地對(duì)最新的圖數(shù)據(jù)進(jìn)行在線處理,從而得到準(zhǔn)實(shí)時(shí)的分析結(jié)果。然而實(shí)現(xiàn)準(zhǔn)實(shí)時(shí)分析,數(shù)據(jù)的處理延遲需要足夠低。此外,在分布式環(huán)境下,還需保持動(dòng)態(tài)數(shù)據(jù)訪問(wèn)的全局一致性,從而保證分析結(jié)果的正確性。為此,我們?cè)O(shè)計(jì)了動(dòng)態(tài)演化圖在線分析子系統(tǒng)。該子系統(tǒng)的架構(gòu)的設(shè)計(jì)考慮了處理流程的耦合關(guān)系,對(duì)圖數(shù)據(jù)存儲(chǔ)和分析計(jì)算進(jìn)行了解耦。它選用了一個(gè)“時(shí)段提交”技術(shù)來(lái)處理圖更新,并為系統(tǒng)的計(jì)算部分提出了全新的增量計(jì)算模型,大大降低分析計(jì)算的延遲。我們完成了該系統(tǒng)的工程實(shí)現(xiàn),并在1億條真實(shí)推特文本數(shù)據(jù)上進(jìn)行了包括爭(zhēng)議話題探測(cè)、近似最短路徑計(jì)算、用戶排序等多種應(yīng)用的測(cè)試。利用40臺(tái)機(jī)器組成的集群,我們獲得了10萬(wàn)每秒的推文處理速率,并保持2.5分鐘以內(nèi)的數(shù)據(jù)延遲,滿足了我們最初設(shè)定的“遠(yuǎn)超推文的產(chǎn)生速率”的性能要求。 二、動(dòng)態(tài)演化圖離線分析的系統(tǒng)問(wèn)題。在該問(wèn)題中,系統(tǒng)需要保存動(dòng)態(tài)演化圖的長(zhǎng)期歷史數(shù)據(jù),并支持動(dòng)態(tài)演化圖長(zhǎng)期變化趨勢(shì)的離線分析。相對(duì)于靜態(tài)圖分析處理的是單一的靜態(tài)圖,長(zhǎng)時(shí)間跨度動(dòng)態(tài)演化圖分析面對(duì)的是多個(gè)時(shí)間點(diǎn)對(duì)應(yīng)的一系列靜態(tài)圖。更大的數(shù)據(jù)量帶來(lái)更高的處理開(kāi)銷,因而系統(tǒng)分析計(jì)算的性能非常重要。此外,系統(tǒng)還需要為動(dòng)態(tài)演化圖復(fù)雜多變的存取模式提供高效的訪問(wèn)性能,為分析性能提供保障。為此我們?cè)谖闹刑岢隽藙?dòng)態(tài)演化圖離線分析子系統(tǒng)。它的副本相異數(shù)據(jù)排布技術(shù)利用數(shù)據(jù)中心多個(gè)數(shù)據(jù)備份的特點(diǎn),為動(dòng)態(tài)演化圖不同類型的訪問(wèn)提供不同針對(duì)性的數(shù)據(jù)組織方式,從而在復(fù)雜多變的存取訪問(wèn)中獲得更好的數(shù)據(jù)存取性能;利用全新的局部性感知分批調(diào)度技術(shù)——局部性分批調(diào)度,我們提高了分析計(jì)算中高速緩存的利用率并減少了數(shù)據(jù)同步的開(kāi)銷,極大地改善了長(zhǎng)時(shí)間跨度動(dòng)態(tài)演化圖分析的整體性能。在實(shí)際大規(guī)模動(dòng)態(tài)演化圖進(jìn)行的多項(xiàng)應(yīng)用測(cè)試結(jié)果表明,該系統(tǒng)能夠提供相對(duì)于目前數(shù)據(jù)庫(kù)系統(tǒng)高達(dá)5倍的存取性能,以及相對(duì)于靜態(tài)圖分析平臺(tái)高達(dá)10倍的性能。 綜上,本論文所述的研究,為圖分析平臺(tái)的發(fā)展進(jìn)步,特別是動(dòng)態(tài)演化圖數(shù)據(jù)分析平臺(tái)領(lǐng)域,做出了積極的探索。
【學(xué)位授予單位】：中國(guó)科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：TP333

【共引文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 郎波;張博宇;;面向大數(shù)據(jù)的非結(jié)構(gòu)化數(shù)據(jù)管理平臺(tái)關(guān)鍵技術(shù)[J];信息技術(shù)與標(biāo)準(zhǔn)化;2013年10期

2 邵景峰;崔尊民;王進(jìn)富;白曉波;;大數(shù)據(jù)下紡織制造執(zhí)行系統(tǒng)的構(gòu)建[J];紡織器材;2013年06期

3 張亞楠;譚躍生;;基于MapReduce的并行遮蓋文本聚類算法[J];內(nèi)蒙古科技大學(xué)學(xué)報(bào);2013年03期

4 周國(guó)亮;朱永利;王桂蘭;;CC-MRSJ:Hadoop平臺(tái)下緩存敏感的星型聯(lián)接算法[J];電信科學(xué);2013年10期

5 劉喜文;鄭昌興;王文龍;湯剛強(qiáng);;構(gòu)建數(shù)據(jù)倉(cāng)庫(kù)過(guò)程中的數(shù)據(jù)清洗研究[J];圖書與情報(bào);2013年05期

6 楊震;徐敏捷;劉璋峰;秦達(dá);姚曉輝;;語(yǔ)音大數(shù)據(jù)信息處理架構(gòu)及關(guān)鍵技術(shù)研究[J];電信科學(xué);2013年11期

7 潘善亮;茅琴嬌;韓露;;一種基于虛擬社交化的Web服務(wù)發(fā)現(xiàn)方法研究[J];電信科學(xué);2013年12期

8 王鵬;黃焱;劉峰;安俊秀;;大數(shù)據(jù)技術(shù)中計(jì)算與數(shù)據(jù)的協(xié)作機(jī)制[J];成都信息工程學(xué)院學(xué)報(bào);2014年01期

9 杜政頡;王鵬;黃焱;郎福通;;一種基于Storm編程模型的迭代Topology方案[J];成都信息工程學(xué)院學(xué)報(bào);2014年01期

10 范飛;黃文明;鄧珍榮;;Oozie工作流在Mahout分布式數(shù)據(jù)挖掘中的應(yīng)用[J];桂林電子科技大學(xué)學(xué)報(bào);2014年01期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前6條

1 喬媛媛;劉芳;凌艷;尹勁松;;云計(jì)算環(huán)境下MapReduce的資源建模與性能預(yù)測(cè)[A];2013年全國(guó)通信軟件學(xué)術(shù)會(huì)議論文集[C];2013年

2 徐子偉;張陳斌;陳宗海;;大數(shù)據(jù)技術(shù)概述[A];系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)論文集（第15卷）[C];2014年

3 Xiaoguang Han;Jigang Sun;Wu Qu;Xuanxia Yao;;Distributed Malware Detection based on Binary File Features in Cloud Computing Environment[A];第26屆中國(guó)控制與決策會(huì)議論文集[C];2014年

4 陳佐旗;余柏蒗;吳健平;;基于GPU通用計(jì)算的遙感數(shù)據(jù)處理——以計(jì)算地表太陽(yáng)輻射值為例[A];第十八屆中國(guó)環(huán)境遙感應(yīng)用技術(shù)論壇論文集[C];2014年

5 白永超;付偉;辛陽(yáng);;基于Hadoop和Nutch的分布式搜索引擎研究與仿真[A];第十九屆全國(guó)青年通信學(xué)術(shù)年會(huì)論文集[C];2014年

6 李超越;徐國(guó)勝;;Hadoop公平調(diào)度算法的改進(jìn)[A];第十九屆全國(guó)青年通信學(xué)術(shù)年會(huì)論文集[C];2014年

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 劉馨月;Web挖掘中的鏈接分析與話題檢測(cè)研究[D];大連理工大學(xué);2012年

2 馬飛;云數(shù)據(jù)中心中虛擬機(jī)放置和實(shí)時(shí)遷移研究[D];北京交通大學(xué);2013年

3 樂(lè)承毅;企業(yè)知識(shí)與員工知識(shí)貢獻(xiàn)度集成評(píng)價(jià)方法及應(yīng)用研究[D];浙江大學(xué);2013年

4 孫甲申;基于主題模型和隨機(jī)游走的標(biāo)簽技術(shù)研究[D];北京郵電大學(xué);2013年

5 張鵬;數(shù)據(jù)中心網(wǎng)絡(luò)的流量管理和優(yōu)化問(wèn)題研究[D];北京郵電大學(xué);2013年

6 孫茂華;安全多方計(jì)算及其應(yīng)用研究[D];北京郵電大學(xué);2013年

7 李健;云計(jì)算環(huán)境下最小化運(yùn)營(yíng)開(kāi)銷的調(diào)度技術(shù)研究[D];北京郵電大學(xué);2013年

8 龔書;抽取式多文檔文摘的文本表示研究[D];北京交通大學(xué);2013年

9 張帆;認(rèn)知可重構(gòu)的高效能Web服務(wù)體系結(jié)構(gòu)研究[D];解放軍信息工程大學(xué);2013年

10 尹莉;基礎(chǔ)數(shù)學(xué)領(lǐng)域作者合作網(wǎng)絡(luò)實(shí)證分析[D];西北大學(xué);2013年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 耿玉嬌;MapReduce中基于抽樣技術(shù)的傾斜問(wèn)題研究[D];大連海事大學(xué);2013年

2 芮虎;比價(jià)購(gòu)物平臺(tái)中網(wǎng)絡(luò)爬蟲的設(shè)計(jì)與實(shí)現(xiàn)[D];華東理工大學(xué);2013年

3 王梓;林產(chǎn)品貿(mào)易信息用戶興趣模型及個(gè)性化搜索[D];北京林業(yè)大學(xué);2013年

4 牛雷;分布式多媒體平臺(tái)中視頻搜索技術(shù)的研究與應(yīng)用[D];北京郵電大學(xué);2013年

5 林哲;面向行業(yè)的信息融合原型系統(tǒng)的研究與實(shí)現(xiàn)[D];北京郵電大學(xué);2013年

6 萬(wàn)德穩(wěn);藏文搜索和搜索結(jié)果聚類研究及系統(tǒng)實(shí)現(xiàn)[D];西南交通大學(xué);2013年

7 閻正喜;H基金公司網(wǎng)上交易系統(tǒng)安全問(wèn)題研究[D];西南交通大學(xué);2013年

8 顏志博;基于用戶反饋的關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵詞搜索技術(shù)研究[D];黑龍江大學(xué);2012年

9 張婧;面向云計(jì)算運(yùn)營(yíng)管理的資源預(yù)測(cè)模型[D];西北大學(xué);2013年

10 黃佳;比較購(gòu)物搜索引擎的研究與應(yīng)用[D];武漢理工大學(xué);2013年

，

本文編號(hào)：1305529