本文關(guān)鍵詞：大規(guī)模實時數(shù)據(jù)流連接關(guān)鍵技術(shù)的研究

  更多相關(guān)文章： 實時數(shù)據(jù)流 連接 Compressed直方圖 一致性hash (key valueList) 共享時間片

【摘要】：互聯(lián)網(wǎng)、傳感器以及物聯(lián)網(wǎng)等技術(shù)的發(fā)展,使數(shù)據(jù)產(chǎn)生的速度越來越快。無處不在的數(shù)據(jù)中隱藏著各種有價值的信息,這些信息給人們的日常生活提供了便利。 在很多應(yīng)用中,信息以數(shù)據(jù)流的形式提供給用戶,這些信息帶有很強的時效性,要求用戶以"on-the-fly"的形式進(jìn)行處理。另外,由于設(shè)備以及應(yīng)用特點的限制,單條數(shù)據(jù)流往往只能提供部分?jǐn)?shù)據(jù),用戶需要將多條數(shù)據(jù)流結(jié)合起來才能獲取完整信息。連接(Join)作為獲取綜合信息的有效手段之一,在數(shù)據(jù)流處理中占有重要地位。 大數(shù)據(jù)時代的到來使單節(jié)點的計算模式已經(jīng)不能滿足數(shù)據(jù)流連接的需求,由多個‘'shared-nothing"廉價節(jié)點構(gòu)成的集群成為解決該問題的有效手段之一。本文在深入研究和總結(jié)相關(guān)工作的基礎(chǔ)上,圍繞分布式環(huán)境下多路數(shù)據(jù)流的連接問題展開研究,內(nèi)容主要集中在以下幾個方面： 首先,在數(shù)據(jù)流模型下提出了基于增量計算的Compressed直方圖構(gòu)建和維護(hù)算法。在允許的誤差范圍內(nèi),Compressed直方圖可以反映當(dāng)前滑動窗口中數(shù)據(jù)的大致分布情況,為接下來多路數(shù)據(jù)流的連接優(yōu)化問題提供支持,該部分為后面研究的基礎(chǔ)。 其次,針對二路數(shù)據(jù)流的特點提出了基于流水線的二路數(shù)據(jù)流連接算法。該算法將計算節(jié)點以線性形式組織,將兩條數(shù)據(jù)流以相向的方式注入流水線,可以處理二路數(shù)據(jù)流等值及不等值連接,在不需要數(shù)據(jù)備份的條件下能夠保證結(jié)果的完整性。另外,在流水線模型下提出了基于上游備份的容錯機制、類似按壓橡皮泥的負(fù)載均衡機制以及可擴(kuò)展性機制等。 再次,針對多路數(shù)據(jù)流等值連接的特點提出了基于一致性hash的多路數(shù)據(jù)流等值連接分配算法,該算法在保證相關(guān)聯(lián)元組能夠分配到相同節(jié)點的前提下,可以維持各個計算節(jié)點間的負(fù)載均衡。另外,根據(jù)直方圖提供的信息,在數(shù)據(jù)流連接過程中采用基于貪心的算法實時維持連接樹,保證數(shù)據(jù)流以相對較優(yōu)的順序執(zhí)行,減少網(wǎng)絡(luò)傳輸及連接過程的執(zhí)行時間。 最后,對通用性更強的多路數(shù)據(jù)流非等值連接進(jìn)行了研究,提出了基于范圍hash和共享時間片的分配策略。這兩個策略在兼顧結(jié)果完整性和負(fù)載均衡的同時,也盡量減少備份數(shù)據(jù)的傳遞量,降低網(wǎng)絡(luò)負(fù)載。另外,針對很多應(yīng)用滑動窗口中連接屬性屬于多重集的情況,提出了基于(key,valueList)的"Group Join"連接算法,降低網(wǎng)絡(luò)傳輸量,在某些情況下減少執(zhí)行時間。 本文從分布式多路數(shù)據(jù)流連接出發(fā),提出了適合二路數(shù)據(jù)流連接的流水線算法、適合等值連接的一致性hash算法以及適合非等值連接的范圍hash和共享時間片算法,并在這些算法的基礎(chǔ)上提出了一系列的負(fù)載均衡、容錯、擴(kuò)容以及連接優(yōu)化算法,為后續(xù)研究研究工作提供了參考。
【關(guān)鍵詞】：實時數(shù)據(jù)流 連接 Compressed直方圖 一致性hash (key valueList) 共享時間片
【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：TP311.13
【目錄】：

• 摘要5-7
• ABSTRACT7-9
• 目錄9-12
• 插圖索引12-14
• 算法索引14-15
• 第一章 緒論15-25
• 1.1 論文研究背景15-18
• 1.1.1 大數(shù)據(jù)產(chǎn)生背景15-16
• 1.1.2 數(shù)據(jù)流概念及特征16-17
• 1.1.3 主流數(shù)據(jù)流計算環(huán)境17-18
• 1.2 論文研究問題的提出18-22
• 1.2.1 數(shù)據(jù)流直方圖的高效構(gòu)建方法20
• 1.2.2 分布式環(huán)境下二路數(shù)據(jù)流連接20-21
• 1.2.3 多路數(shù)據(jù)流等值連接21
• 1.2.4 多路數(shù)據(jù)流任意連接21-22
• 1.3 論文的主要研究工作22-24
• 1.3.1 論文的研究內(nèi)容22
• 1.3.2 論文的組織結(jié)構(gòu)22-24
• 1.4 本章小結(jié)24-25
• 第二章 數(shù)據(jù)流連接相關(guān)技術(shù)綜述25-39
• 2.1 引言25-26
• 2.2 數(shù)據(jù)流相關(guān)技術(shù)26-30
• 2.2.1 定義及分類26-27
• 2.2.2 滑動窗口27
• 2.2.3 時間戳27-28
• 2.2.4 多路數(shù)據(jù)流連接語義28-30
• 2.3 數(shù)據(jù)流連接算法30-37
• 2.3.1 單節(jié)點上多路數(shù)據(jù)流連接算法30-32
• 2.3.2 分布式環(huán)境下多路數(shù)據(jù)流連接算法32-37
• 2.4 本章小結(jié)37-39
• 第三章 數(shù)據(jù)流Compressed直方圖構(gòu)建算法39-51
• 3.1 引言39-40
• 3.2 背景及相關(guān)工作40-42
• 3.2.1 直方圖定義及分類40-41
• 3.2.2 相關(guān)工作41-42
• 3.3 基于增量計算的Compressed直方圖構(gòu)建算法42-45
• 3.3.1 Compressed直方圖構(gòu)建算法42
• 3.3.2 基于增量計算的直方圖維護(hù)策略42-45
• 3.4 實驗及分析45-49
• 3.4.1 重構(gòu)與維護(hù)時間對比46-47
• 3.4.2 誤差因素47-49
• 3.5 本章小結(jié)49-51
• 第四章 二路數(shù)據(jù)流連接算法設(shè)計51-65
• 4.1 引言51-52
• 4.2 背景及相關(guān)工作介紹52-53
• 4.3 基于流水線的二路數(shù)據(jù)流連接算法53-60
• 4.3.1 流水線連接基本原理53-54
• 4.3.2 基于流水線連接算法54-56
• 4.3.3 容錯機制56-59
• 4.3.4 可擴(kuò)展性59-60
• 4.4 實驗及結(jié)果分析60-64
• 4.4.1 流水線模型處理能力61-62
• 4.4.2 負(fù)載均衡62-63
• 4.4.3 容錯能力63-64
• 4.5 本章小結(jié)64-65
• 第五章 多路數(shù)據(jù)流等值連接算法設(shè)計65-85
• 5.1 引言65-66
• 5.2 背景及相關(guān)工作介紹66-68
• 5.2.1 多路數(shù)據(jù)流連接分配問題66-67
• 5.2.2 連接效率問題67-68
• 5.3 基于一致性Hash的多路數(shù)據(jù)流分配算法68-73
• 5.3.1 負(fù)載均衡68-71
• 5.3.2 災(zāi)難恢復(fù)71-73
• 5.4 基于貪心的多路數(shù)據(jù)流連接73-77
• 5.4.1 基于貪心的連接樹構(gòu)建算法74-76
• 5.4.2 簡單貪心連接樹構(gòu)建算法76-77
• 5.5 實驗及分析77-84
• 5.5.1 負(fù)載均衡77-80
• 5.5.2 容錯80-81
• 5.5.3 多路數(shù)據(jù)流連接順序優(yōu)化81-83
• 5.5.4 運算時間83-84
• 5.6 本章小結(jié)84-85
• 第六章 多路數(shù)據(jù)流任意連接算法設(shè)計85-105
• 6.1 引言85-86
• 6.2 背景及相關(guān)工作介紹86-88
• 6.2.1 多路數(shù)據(jù)流任意連接分配問題86-87
• 6.2.2 多路數(shù)據(jù)流連接問題87-88
• 6.3 多路數(shù)據(jù)流任意連接分配算法88-92
• 6.3.1 范圍hash分配算法88-89
• 6.3.2 基于時間片分配算法89-92
• 6.4 基于(key,ualueList)的多路數(shù)據(jù)流連接92-96
• 6.4.1 網(wǎng)絡(luò)傳輸93-94
• 6.4.2 連接操作94-96
• 6.5 實驗及結(jié)果分析96-103
• 6.5.1 負(fù)載均衡97-99
• 6.5.2 (key,value)(?)(key,valueList)99-103
• 6.6 本章小結(jié)103-105
• 第七章 總結(jié)與展望105-109
• 7.1 本文工作總結(jié)105-106
• 7.2 貢獻(xiàn)及創(chuàng)新點106
• 7.3 展望106-109
• 參考文獻(xiàn)109-115
• 致謝115-117
• 在讀期間發(fā)表的學(xué)術(shù)論文與取得的研究成果117

【共引文獻(xiàn)】

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

1 李丹;郭放;;節(jié)能變壓器制造系統(tǒng)中的數(shù)據(jù)流管理系統(tǒng)研究[J];變壓器;2009年02期

2 谷峪;李曉靜;許嘉;于戈;;支持復(fù)雜語義的數(shù)據(jù)流滑動窗口連接建模和查詢優(yōu)化[J];東北大學(xué)學(xué)報(自然科學(xué)版);2008年11期

3 趙文;劉學(xué)洋;劉殿興;王立福;;一種基于Trie樹和擴(kuò)展B樹的RFID標(biāo)簽編碼過濾方法研究[J];電子學(xué)報;2011年S1期

4 蔣濤;高云君;張彬;周傲英;樂光學(xué);;不確定數(shù)據(jù)查詢處理[J];電子學(xué)報;2013年05期

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

6 劉崇富;張子鋒;孔浩;;基于J2EE架構(gòu)的高校檔案管理日志模塊的設(shè)計與實現(xiàn)[J];電腦開發(fā)與應(yīng)用;2014年01期

7 孫剛;周華平;孫克雷;;基于改進(jìn)的隨機決策樹的煤礦安全評價方法[J];阜陽師范學(xué)院學(xué)報(自然科學(xué)版);2014年02期

8 田文飚;康健;張洋;芮國勝;張海波;;基于卡爾曼濾波的壓縮感知弱匹配去噪重構(gòu)[J];電子學(xué)報;2014年06期

9 梁源;王興華;向新;王鋒;孫曄;;一種基于貪婪算法的CORDIC改進(jìn)算法[J];電訊技術(shù);2014年03期

10 劉文才;黃薇;;淺析算法優(yōu)化[J];電子制作;2014年09期

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

1 潘鵬;Deep Web查詢中的不確定性問題研究[D];山東大學(xué);2010年

2 朱輝生;基于情節(jié)規(guī)則匹配的數(shù)據(jù)流預(yù)測研究[D];復(fù)旦大學(xué);2011年

3 侯東風(fēng);流式數(shù)據(jù)多維建模與查詢關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2010年

4 甘亮;面向網(wǎng)絡(luò)安全監(jiān)控的流數(shù)據(jù)處理技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2011年

5 陳濤;大規(guī)模網(wǎng)絡(luò)存儲環(huán)境中的數(shù)據(jù)布局與查詢優(yōu)化技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2011年

6 鄧華鋒;分布式數(shù)據(jù)流處理的算子調(diào)度與負(fù)載平衡研究[D];華中科技大學(xué);2007年

7 李俊奎;時間序列相似性問題研究[D];華中科技大學(xué);2008年

8 蘇亮;數(shù)據(jù)流分析關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2008年

9 孟和;無線內(nèi)容下載平臺中事件流處理應(yīng)用研究[D];天津大學(xué);2009年

10 吳楓;數(shù)據(jù)流挖掘若干關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2009年

  本文關(guān)鍵詞：大規(guī)模實時數(shù)據(jù)流連接關(guān)鍵技術(shù)的研究

  更多相關(guān)文章： 實時數(shù)據(jù)流 連接 Compressed直方圖 一致性hash (key valueList) 共享時間片

，

本文編號：512060