"《大數據算法設計與分析》以大數據基礎研究與大數據應用為背景，以大數據算法設計與分析方法學為主線，以多個重要大數據計算問題為例，全面、繫統、深入地介紹大數據算法設計與分析的原理與方法。?著作的內容包括大數據算法方面的近期新和最重要研究成果，全面反映大數據算法研究的新進展。?著作注重理論與實際相結合，以具有實際應用背景的大數據計算問題為例，既細致地介紹其求解算法的設計方法，又對算法的正確屬性和復雜性進行精致的理論分析，使得讀者不僅掌握求解重要大數據計算問題的大數據算法的設計和分析方法，等

●第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
第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
……

《大數據算法設計與分析》以大數據為背景，以求解大數據計算問題的計算方法（即亞線性時間計算方法、壓縮計算方法、抽樣計算方法、增量式計算方法、分布式並行計算方法）為主線，繫統地介紹大數據計算問題求解算法的設計與分析的理論與方法，主要包括: 大數據計算問題的復雜性分類、大數據計算問題的亞線性時間求解算法的設計與分析方法、基於抽樣的大數據計算問題的求解算法的設計與分析方法、基於數據壓縮的大數據計算問題的求解算法的設計與分析方法、大數據計算問題的增量式求解算法的設計與分析方法、大數據計算問題的分布式並行求解算法的設計與分析方法。本書以作者在大數據計算方面的研究成果為主，也覆蓋了大數據算法研究領域的部分新研究成果。本書可以作為高等學校數據科學與大數據技術專業和計算機科學與技術專業高年級本科生或研究生的大數據算法課程的教材，也可以作為大數據研究人員的參考書。

李建中 著