大數(shù)據(jù)復(fù)雜查詢技術(shù)研究

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