大數據算法設計與分析

本書以大數據為背景，以求解大數據計算問題的計算方法（即亞線性時間計算方法、壓縮計算方法、抽樣計算方法、增量式計算方法、分散式平行計算方法）為主線，系統地介紹大數據計算問題求解演算的設計與分析的理論與方法，主要包括：大數據計算問題的複雜性分類、大數據計算問題的亞線性時間求解演算的設計與分析方法、基於抽樣的大數據計算問題的求解演算的設計與分析方法、基於數據壓縮的大數據計算問題的求解演算的設計與分析方法、大數據計算問題的增量式求解演算的設計與分析方法、大數據計算問題的分散式並行求解演算的設計與分析方法。

本書以作者在大數據計算方面的研究成果為主，也覆蓋了大數據演算研究領域的部分新研究成果。本書可以作為高等學校數據科學與大數據技術專業和電腦科學與技術專業高年級本科生或研究生的大數據演算課程的教材，也可以作為大數據研究人員的參考書。

第1章 緒論
1.1 大樹據、大樹據算法與大樹據計算
1.2 大樹據計算的挑戰和研究問題
1.2.1 大樹據計算的挑戰
1.2.2 大樹據計算的研究問題
1.3 大樹據計算複雜性理論和算法的研究進展
1.3.1 大樹據計算複雜性理論的研究進展
1.3.2 大樹據算法設計方法的研究進展
1.3.3 大樹據計算問題求解算法的研究進展
1.4 本章參考文獻
1.4.1 本章參考文獻注釋
1.4.2 本章參考文獻列表

第2章 大樹據計算問題的複雜性
2.1 隨機存取圖靈機
2.1.1 確定隨機存取圖靈機
2.1.2 通用隨機存取圖靈機
2.2 大樹據計算問題的複雜性與分類
2.2.1 大樹據計算問題的複雜性
2.2.2 單純易解性大樹據計算問題類
2.2.3 偽易解性大樹據計算問題類
2.3 歸約與大樹據計算問題的 性
2.3.1 DLOGTIME歸約
2.3.2 大樹據計算問題的 性
2.4 本章參考文獻
2.4.1 本章參考文獻注釋
2.4.2 本章參考文獻列表

第3章 大樹據的亞線性時間計算方法
3.1 亞線性時間算法基礎
3.1.1 亞線性時間算法的基本概念
3.1.2 樹學基礎
3.2 單純亞線性時間 算法
3.2.1 後繼搜索算法
3.2.2 德洛奈三角剖分中的點定位算法
3.3 偽亞線性時間 算法
3.3.1 Skyline問題的求解算法
3.3.2 Top-k支配集問題的求解算法
3.4 亞線性時間近似算法
3.4.1 小生成樹代價近似求解算法
3.4.2 樹據不一致性近似評估算法
3.4.3 歐幾裡得空間中 近鄰近似求解算法
3.5 本章參考文獻
3.5.1 本章參考文獻注釋
3.5.2 本章參考文獻列表

第4章 大樹據的抽樣計算方法
4.1 抽樣計算方法概述
4.2 圖的平均參樹估計算法
4.2.1 預備知識
4.2.2 平均度求解算法
4.2.3 平均單源距離求解算法
4.2.4 平均頂點距離求解算法