大數據復雜查詢技術研究

目錄
前言
第1章 緒論 1
第2章 云數據管理中多維索引與復雜查詢 4
2.1 概述 4
2.2 云數據管理中多維索引技術 4
2.2.1 云數據管理索引技術研究概述 5
2.2.2 基于分布式文件系統的索引 6
2.2.3 基于key-value存儲的索引 14
2.2.4 針對不同數據類型的索引技術 19
2.3 空間關鍵字查詢 27
2.3.1 兩階段索引 27
2.3.2 空間文本混合索引 28
2.3.3 空間關鍵字查詢擴展 30
2.4 可擴展的相似性連接查詢 31
2.4.1 集合相似性連接查詢 32
2.4.2 向量相似性連接查詢 36
2.4.3 空間數據相似性連接查詢 40
2.4.4 概率數據相似性連接查詢 41
2.4.5 字符串相似性連接查詢 43
2.4.6 圖數據相似性連接查詢 43
2.5 本章小結 44
第3章 云環(huán)境下針對物聯網數據的多維索引技術 45
3.1 概述 45
3.2 MLM-Index 47
3.2.1 MLM-Index概述 47
3.2.2 MLM-Index關鍵技術 49
3.2.3 MLM-Index索引實現 53
3.2.4 基于MLM-Index的查詢處理 55
3.2.5 實驗分析 58
3.3 混合索引 65
3.3.1 混合索引概述 65
3.3.2 全局索引 66
3.3.3 局部索引 67
3.3.4 基于混合索引的查詢處理 68
3.3.5 實驗分析 71
3.4 本章小結 74
第4章 可擴展的空間關鍵字查詢 75
4.1 概述 75
4.2 空間關鍵字查詢的定義 77
4.3 基于空間和文本的混合索引方案 78
4.3.1 STbHI結構 78
4.3.2 查詢處理 80
4.3.3 優(yōu)化方案 82
4.4 基于詞聚類的倒排空間索引方案 83
4.5 實驗分析 87
4.5.1 實驗設置 87
4.5.2 改變數據集大小 88
4.5.3 改變查詢詞個數 90
4.5.4 改變查詢范圍 90
4.6 本章小結 91
第5章 基于MapReduce的概率集合相似性連接查詢 92
5.1 概述 92
5.2 集合相似性連接查詢的相關工作 93
5.3 問題定義 94
5.3.1 集合級的概率集合數據庫 94
5.3.2 概率集合相似性連接查詢 94
5.4 基本的嵌套循環(huán)連接算法 95
5.4.1 BNLJ算法描述 95
5.4.2 代價分析 96
5.5 基于概率的前綴過濾算法 97
5.5.1 概率計算分析 97
5.5.2 基于概率的項頻度排序 98
5.5.3 聯合前綴過濾 99
5.5.4 基于Map端過濾的相似性連接查詢算法 100
5.5.5 基于Reduce端過濾的相似性連接查詢算法 102
5.5.6 基于混合過濾的相似性連接查詢算法 103
5.6 實驗分析 103
5.7 本章小結 107
第6章 大規(guī)模高維向量相似性連接查詢 108
6.1 概述 108
6.2 問題定義及基礎知識 110
6.2.1 問題定義 110
6.2.2 基礎知識 110
6.3 基于SAX的高維向量相似性連接查詢算法 113
6.3.1 SAX-HDSJ算法概述 113
6.3.2 SAX-HDSJ算法詳細流程 113
6.3.3 SAX-HDSJ算法代價分析 117
6.4 高維向量相似性連接查詢改進算法 120
6.4.1 改進的SAX-HDSJ算法概述 121
6.4.2 基于SAX的數據劃分 121
6.5 實驗分析 122
6.5.1 實驗環(huán)境設置 122
6.5.2 不同維度下的性能 123
6.5.3 不同閾值下的性能 124
6.5.4 不同數據規(guī)模下的性能 125
6.5.5 均勻數據集和傾斜數據集上的性能 127
6.6 基于多PAA過濾的相似性連接查詢算法 128
6.6.1 基于單PAA的向量相似性連接查詢 128
6.6.2 基于多PAA的向量相似性連接查詢 130
6.6.3 基于SAX的多PAA的向量相似性連接查詢 132
6.6.4 參數選擇 134
6.6.5 實驗分析 138
6.7 本章小結 142
第7章 Top-k相似性連接查詢 143
7.1 概述 143
7.2 問題定義 143
7.3 基于閾值的Top-k相似性連接查詢 144
7.4 基于SAX的Top-k相似性連接查詢 144
7.4.1 查詢框架 144
7.4.2 實現流程 145
7.4.3 實驗分析 149
7.5 基于閾值估計的Top-k相似性連接查詢 154
7.5.1 海量高維向量相似度分布直方圖估計 154
7.5.2 Top-k閾值估計 155
7.5.3 基于閾值估計的Top-k相似性連接查詢算法 156
7.5.4 實驗分析 157
7.6 本章小結 161
第8章 基于隨機映射的相似性連接查詢 162
8.1 概述 162
8.2 問題定義與基礎知識 162
8.3 基于單映射的并行相似性連接查詢 167
8.4 基于多映射的并行相似性連接查詢 169
8.5 基于映射空間劃分的并行相似性連接查詢 172
8.5.1 基于映射空間劃分的相似性連接查詢框架 172
8.5.2 基于MapReduce的相似性連接查詢實現 173
8.6 面向傾斜數據的相似性連接查詢 175
8.6.1 面向負載均衡的相似性連接查詢 175
8.6.2 基于距離劃分樹的相似性連接查詢 177
8.6.3 基于二維映射空間劃分的相似性連接查詢 181
8.7 本章小結 182
第9章 相似性連接查詢其他問題 183
9.1 概述 183
9.2 負載均衡 183
9.2.1 相似度計算負載評估模型 183
9.2.2 相似性連接負載均衡策略 184
9.3 多源數據相似性連接查詢 184
9.3.1 相似性連接查詢結果大小估計 185
9.3.2 多源數據相似性連接順序選擇策略 185
9.3.3 多源高維大數據相似性連接查詢算法 186
9.4 基于LSH的KNN相似性連接查詢 186
9.4.1 LSH函數學習 187
9.4.2 基于LSH的并行近似KNN連接查詢 188
9.4.3 KNN相似性連接查詢改進方案 189
9.5 本章小結 190
第10章 大數據復雜查詢面臨的挑戰(zhàn) 191
10.1 大數據多維索引技術 191
10.2 大數據復雜查詢處理技術 193
參考文獻 195