大数据复杂查询技术研究

目录
前言
第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章 云环境下针对物联网数据的多维索引技术 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 优化方案 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 基本的嵌套循环连接算法 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章 大规模高维向量相似性连接查询 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 实验环境设置 122
6.5.2 不同维度下的性能 123
6.5.3 不同阈值下的性能 124
6.5.4 不同数据规模下的性能 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章 大数据复杂查询面临的挑战 191
10.1 大数据多维索引技术 191
10.2 大数据复杂查询处理技术 193
参考文献 195