大數據算法設計與分析

目錄

第1章緒論1

1.1大數據、大數據算法與大數據計算2

1.2大數據計算的挑戰和研究問題3

1.2.1大數據計算的挑戰3

1.2.2大數據計算的研究問題6

1.3大數據計算復雜性理論和算法的研究進展7

1.3.1大數據計算復雜性理論的研究進展7

1.3.2大數據算法設計方法的研究進展10

1.3.3大數據計算問題求解算法的研究進展12

1.4本章參考文獻17

1.4.1本章參考文獻註釋17

1.4.2本章參考文獻列表17

第2章大數據計算問題的復雜性26

2.1隨機存取圖靈機26

2.1.1確定隨機存取圖靈機26

2.1.2通用隨機存取圖靈機29

2.2大數據計算問題的復雜性與分類33

2.2.1大數據計算問題的復雜性33

2.2.2單純易解性大數據計算問題類35

2.2.3偽易解性大數據計算問題類39

2.3歸約與大數據計算問題的完全性41

2.3.1DLOGTIME歸約41

2.3.2大數據計算問題的完全性44

2.4本章參考文獻44

2.4.1本章參考文獻註釋44

2.4.2本章參考文獻列表45

〖1〗〖1〗第3章大數據的亞線性時間計算方法46

3.1亞線性時間算法基礎46

3.1.1亞線性時間算法的基本概念46

3.1.2數學基礎50

3.2單純亞線性時間精確算法54

3.2.1後繼搜索算法54

3.2.2德洛奈三角剖分中的點定位算法56

3.3偽亞線性時間精確算法62

3.3.1Skyline問題的求解算法62

3.3.2Topk支配集問題的求解算法66

3.4亞線性時間近似算法75

3.4.1最小生成樹代價近似求解算法76

3.4.2數據不一致性近似評估算法83

3.4.3歐幾里得空間中最近鄰近似求解算法91

3.5本章參考文獻102

3.5.1本章參考文獻註釋102

3.5.2本章參考文獻列表103

第4章大數據的抽樣計算方法105

4.1抽樣計算方法概述105

4.2圖的平均參數估計算法106

4.2.1預備知識106

4.2.2平均度求解算法108

4.2.3平均單源距離求解算法113

4.2.4平均頂點距離求解算法115

4.3無線傳感網感知數據聚集算法118

4.3.1預備知識118

4.3.2基於均勻抽樣的近似聚集算法121

4.3.3基於伯努利抽樣的近似聚集算法137

4.4度量空間上的聚類算法148

4.4.1聚類問題的定義148

4.4.2O(n4.77)時間8近似算法149

4.4.3時間復雜性獨立於輸入大小的近似算法162

4.5本章參考文獻171

4.5.1本章參考文獻註釋171

4.5.2本章參考文獻列表172

第5章大數據的壓縮計算方法173

5.1壓縮計算方法概述173

5.2數據壓縮方法175

5.2.1數據編碼方法176

5.2.2Header壓縮方法179

5.2.3多維數據壓縮方法184

5.2.4哈夫曼編碼方法186

5.3壓縮數據上的轉置算法190

5.3.1問題定義190

5.3.2算法設計191

5.3.3算法分析192

5.4壓縮數據上的聚集算法194

5.4.1問題定義194

5.4.2通用聚集算法195

5.4.3一遍掃描聚集算法199

5.4.4公共前綴聚集算法200

5.4.5公共中綴聚集算法203

5.4.6純前綴聚集算法206

5.5壓縮數據上的Cube算法207

5.5.1數據壓縮和問題定義207

5.5.2算法設計208

5.5.3算法分析220

5.6壓縮圖上的可達性判定算法224

5.6.1問題定義224

5.6.2圖壓縮方法225

5.6.3算法設計227

5.6.4算法分析228

5.7壓縮圖上的圖模式匹配算法229

5.7.1問題定義229

5.7.2圖壓縮方法230

5.7.3算法設計235

5.7.4算法分析235

5.8本章參考文獻236

5.8.1本章參考文獻註釋236

5.8.2本章參考文獻列表237

第6章大數據的增量式計算方法238

6.1增量式計算方法概述238

6.2增量式圖模擬匹配算法241

6.2.1問題定義241

6.2.2圖模擬匹配問題的批量求解算法246

6.2.3增量式常規圖模擬匹配算法251

6.2.4增量式有界圖模擬匹配算法260

6.3增量式數據不一致性檢測算法266

6.3.1問題定義266

6.3.2基於數據垂直劃分的檢測算法270

6.3.3基於數據水平劃分的檢測算法274

6.4增量式數據流查詢處理算法278

6.4.1問題定義278

6.4.2Inc3Agg類算法280

6.4.3Inc5Agg類算法282

6.5增量式數據流近似頻繁項挖掘算法286

6.5.1問題定義287

6.5.2算法設計287

6.5.3算法的正確性與誤差分析289

6.5.4算法的復雜性分析290

6.6增量式物化數據庫視圖維護算法290

6.6.1問題定義290

6.6.2問題的固有時間復雜性291

6.6.3算法設計296

6.6.4算法分析297

6.7本章參考文獻299

6.7.1本章參考文獻註釋299

6.7.2本章參考文獻列表300

第7章大數據的分佈式並行計算方法301

7.1並行計算的基本概念301

7.1.1並行計算系統結構301

7.1.2並行算法及其復雜性分析306

7.2大數據的分佈式存儲方法308

7.2.1一維分佈式存儲方法308

7.2.2多維分佈式存儲方法311

7.2.3分佈式Grid文件316

7.2.4分佈式並行B樹324

7.3分佈式並行排序算法330

7.3.1基於合並操作的分佈式並行排序算法331

7.3.2基於比較交換的分佈式並行排序算法333

7.3.3基於數據劃分的分佈式並行排序算法335

7.4集合操作的分佈式並行算法338

7.4.1集合並的分佈式並行算法338

7.4.2集合交的分佈式並行算法339

7.4.3集合差的分佈式並行算法340

7.5關系代數操作的分佈式並行算法341

7.5.1選擇操作的分佈式並行算法341

7.5.2投影操作的分佈式並行算法344

7.5.3連接操作的分佈式並行算法346

7.6基於CMD的連接操作的分佈式並行連接算法351

7.6.1基本概念351

7.6.2算法CMDJoinHash353

7.6.3算法CMDJoinSortMerge354

7.6.4算法CMDJoinNestedLoop356

7.7基於並行B樹的連接操作的分佈式並行算法357

7.7.1預備知識357

7.7.2基於Range分佈方法的並行B樹連接算法357

7.7.3基於Hash分佈方法的並行B樹連接算法362

7.8本章參考文獻364

7.8.1本章參考文獻註釋364

7.8.2本章參考文獻列表365