本书比较全面地介绍云数据管理中多维索引与复杂查询、云环境下针对物联网数据的多维索引技术、可扩展的空间关键字查询、基于MapReduce的概率集合相似性连接查询、大规模高维向量相似性连接查询、Top-k相似性连接查询、基于随机映射的相似性连接查询、相似性连接查询其他问题、大数据复杂查询面临的挑战等内容。力求向读者系统展示大数据复杂查询领域的最新研究动态，希望能够为从事相关研究的广大读者提供有益的参考和帮助，同时能够为大数据复杂查询相关理论与技术的发展起到一定的促进作用。 本书可作为计算机科学与技术、电子信息科学与技术等相关专业硕士研究生、博士研究生的参考书，也可作为大数据管理与分析研究人员、计算机领域相关研究人员、信息技术相关从业人员的参考书。

第1章 绪论
　　随着物联网、云计算和移动互联网等新型服务的不断涌现，数据以前所未有的速度不断增长和积累。大数据的海量性(volume)、多样性(variety)和高速性(velocity)等特点使得从大数据中快速、准确地获取有价值的信息变得越来越困难。大数据复杂查询与处理主要包括大数据多维索引、可扩展空间关键字查询、大数据相似性连接查询等，是大数据分析的重要研究内容，也是实现大数据价值昀大化的关键，其理论和方法的研究已经成为国内外学术界的研究热点之一，并取得了很多研究成果，但仍然存在诸多挑战。
　　大数据多维索引：在很多应用中，数据都是多维的，如物联网数据一般具有时间、经度、纬度和测量值等属性；电子商务数据一般具有商品名称、商品类别、价格、交易时间等属性。针对这些多维数据，多维查询是一种重要的查询类型，对于分析数据规律、挖掘数据价值具有重要意义。索引是数据管理中的一个重要内容，对于提高查询速度有重要作用。关系型数据库具有成熟的索引技术，如 B+-树、R-树等，能够提供方便快速的多维查询，但是在扩展性方面存在瓶颈。现有的云数据管理系统，能够针对主键(rowkey)提供高效的查询，但是由于缺乏有效的索引技术，对于非主键查询及多维查询无法提供有效支持。因此，探讨云数据管理中的多维索引技术对于提高海量数据的多维查询性能具有重要的研究价值和实际意义。目前，云数据管理中的索引技术已经有一些研究工作，但是现有的方案大都基于 R-树的索引结构，当数据维度比较高、数据量比较大时， R-树的查询性能和数据插入性能都会急剧下降。如何解决上述问题也具有重大挑战。
　　大数据复杂查询：与结构化数据相比，我们称位置数据、图片、视频、轨迹、文本等非结构化数据为复杂数据对象。针对这些复杂数据对象，除了简单的查询，复杂的查询和分析具有更重要的价值与意义。如在基于位置的服务(location-based service，LBS)中，空间关键字查询变得日益重要；集合相似性连接查询在数据集成、实体识别中具有重要的作用；向量相似性连接查询对重复视频检测、图片分类、轨迹聚类等有重要意义。
　　同时，相似性连接查询作为大数据分析的一种重要操作，可以提高相似性检索和数据挖掘的效率，在很多领域得到了广泛应用。相似性连接查询已经有很多研究工作，但是，在大数据时代又产生了一些新的挑战。国际数据公司的研究报告表明，在所有大数据中，视频、音频、图像、文本、基因等非结构化数据占80%以上，它们都是涉及的特征非常多的高维数据，随着数据采集精度的不断提高，其特征可以达到数万维，甚至百万维。美国数学学会组织的“21世纪数学面临的挑战”的学术研讨会上将海量高维数据分析与处理列为一个重要的研究热点问题。随着数据维度的不断增加，现有以索引为基础的过滤模型将不再有效，当维度超过一定阈值时，索引的性能甚至不如顺序扫描。因此，迫切需要设计有效的高维数据相似性连接查询过滤模型，使其能够有效地应对“维度灾难”问题。
　　相似性连接查询是典型的计算密集型操作，随着数据维度的不断增高，两个数据之间相似度的计算代价会比较大；同时，随着数据集合规模的不断扩大，相似性连接查询的时间开销呈指数级增长。传统的集中式处理算法已经无法有效地处理大规模高维数据的相似性连接查询问题。MapReduce并行处理框架因其具有高可扩展性、高容错性和高可用性等特点，逐渐成为海量数据处理的首选方案，为海量高维数据相似性连接查询问题带来了新的机遇。然而， MapReduce也存在一些缺点，如不支持连接查询、存在“木桶效应”、无法有效地处理倾斜数据等，给相似性连接查询带来了新的挑战。因此，亟须研究 MapReduce框架下的相似性连接负载模型和负载均衡策略，并在此基础上设计可扩展的高维数据相似性连接查询算法，有效地处理大规模高维数据。
　　除了数据类型具有多样性，同一数据也很可能来自多个数据源，多源相似性连接查询在实际生活中也有广泛应用。虽然多表连接查询优化已经有大量的研究成果，但是，其不能直接应用于多源相似性连接查询。目前，针对多源高维数据相似性连接查询问题的研究尚未有较好的解决方案。本书将对多源高维数据相似性连接查询中涉及的若干关键问题进行阐述，如高维数据相似性连接查询结果大小估计、相似度分布直方图估计、相似性连接代价模型和多源相似性连接顺序选择策略等。
　　针对上述挑战，本书将对大数据复杂查询与处理相关关键技术进行阐述，主要包括以下内容。
　　大数据多维索引。云数据管理系统由于其高可靠性、高扩展性和高容错性等特点，已经成为大规模数据存储和管理的首选方案，很多企业都把数据部署到云平台下。在很多应用中，数据大都是多维的，如电子商务网站中的商品信息、Flickr中的图片信息、物联网中的传感器数据等。针对这些数据的多维查询或多属性查询是一种常用的查询类型，对数据分析有重要作用。但是，现有的云数据管理系统存在很多局限性，缺乏有效的索引支持，无法提供快速的多维查询，从而限制了其功能和应用范围。本书第3章以海量物联网数据为对象，针对其数据量大、多维、产生速度快等特点，研究在云环境下的多维索引方案，使其既能支持快速的多维查询，又能具有较高的数据插入性能。
　　可扩展的空间关键字查询处理。空间关键字查询在 LBS、地图搜索等应用中是一种重要的查询类型，并且随着空间文本对象数据规模的急剧增加，高效的空间关键字查询处理变得日益重要。现有的空间关键字查询处理方案大都将 R-树和倒排索引相结合，构建混合索引，在混合索引基础上进行过滤和查询。现有方案主要面临两个挑战：一是扩展性不好，无法有效地处理日益增长的大规模空间文本数据，当数据规模越来越大时，索引效率和查询速度都会急剧下降；二是索引更新和维护的代价比较大，无法适应更新频繁、动态变化的应用场景。本书第4章将主要研究在云环境下如何实现可扩展的、高效的空间关键字处理。
　　海量概率集合相似性连接查询。概率集合数据有两个特点：一是每个集合包含若干个集合实例；二是每个集合实例都有一个存在概率。由于这两个特点，概率集合的相似性连接存在一些新的挑战。一方面，在判断两个概率集合是否满足查询要求时，除了考虑各集合实例之间的相似度，还需要考虑集合实例的存在概率，因此，如何将集合实例相似度和集合实例存在概率相结合设计一种新的过滤算法，对于提高概率集合相似性连接查询性能有重要作用。另一方面，常用的基于前缀的过滤方法存在重复比较的问题。如果两个概率集合的集合实例之间有 m个公共元素，那么它们就需要重复比较 m次。本书第5章将结合概率集合数据的特点，对如何避免重复比较、如何设计有效的过滤规则从而提高过滤效果等问题进行深入的研究，并探讨基于 MapReduce框架的并行方案。
　　海量高维向量相似性连接查询。高维向量相似性连接查询在重复视频检测、轨迹聚类、图片分类等方面有重要作用，但存在诸多挑战。一是“维度灾难”问题：传统的方法大都采用基于多维索引(如 R-树)的过滤-验证框架，但是只适合于低维度的向量。当向量的维度比较高时，索引的过滤效果就会变得很差。二是超高维度向量的相似度计算代价比较大：当向量的维度非常高时，两个向量之间的相似度计算代价本身就比较大，成为连接查询性能的一个重要瓶颈。三是数据规模问题方面的挑战：现有的以索引为基础的算法大都是单机算法，无法适应大规模高维向量的计算问题。本书第6～9章将对海量高维向量相似性连接查询技术进行阐述，主要包括基于多重过滤的相似性连接查询、Top-k相似性连接查询、基于随机映射的相似性连接查询和多源相似性连接查询等。
　　第2章 云数据管理中多维索引与复杂查询
　　2.1 概述
　　随着信息技术的飞速发展，在电子商务、物联网、社交网络、计算机仿真、科学计算等众多应用领域，数据量正在以指数级的速度增加，人类已经进入了大数据时代。据统计，全世界的信息量每两年以超过翻倍的速度增长，2011年将产生和复制1.8ZB的海量数据，其增长速度已经超过摩尔定律。传统的关系型数据库虽然能够提供十分成熟的数据存储、索引及查询处理方案，然而面对不断增长的海量数据，关系型数据库在扩展性方面遇到了严重的瓶颈，无法实现高效灵活的扩展。虽然专业的公司能够提供一些针对关系型数据库的扩展方案，但是其部署、管理的代价非常大。
　　自2004年以来，Google公司先后提出了 Google File System[1]、BigTable[2]和 MapReduce[3]等技术。随着这三大技术的提出，云计算作为一种新的海量数据存储、管理、分析模式应运而生，并得到业界众多大公司的广泛应用和深入研究，云计算已经成为海量数据处理的一种标准首选方案。同时也出现了很多优秀的云数据管理系统，如雅虎的 PNUTS[4]、Amazon的 Dynamo[5]、开源的 HBase等。虽然云数据管理系统具有高可扩展性、高可用性和高容错性等特点，但是在索引和复杂查询方面仍存在很多局限性，从而限制了其广泛应用。本章首先介绍云数据管理中已有的索引技术相关研究工作，并对现有工作进行归纳整理与对比分析。然后对几种重要的复杂查询处理技术进行介绍。相似性连接查询主要介绍集合相似性连接查询、向量相似性连接查询及其他类型数据的相似性连接查询，并对现有研究工作的优缺点进行分析。
　　2.2 云数据管理中多维索引技术
　　基于key-value存储的云数据管理技术具有高可扩展性、高可用性和高容错性等特点，能够实现对海量数据的高效存储和处理。然而，现有的基于 key-value存储的云数据管理系统在数据访问方面提供的功能比较简单。云数据管理系统大都按照 rowkey的顺序对数据进行组织，并在 rowkey上建立类似 B+-树的索引结构，所以在 rowkey上能够提供高效的点查询或范围查询。然而针对非 rowkey的查询，它们只能通过全表扫描的方式来实现。虽然我们可以利用 MapReduce技术来实现数据访问的并行化，在一定程度上提高查询速度，但是当数据量非常大时，对于时延要求比较高的应用，全表扫描所需的时间仍然比较长，无法满足实际应用的需求。
　　在实际应用中，除了对 rowkey的查询，还有很多针对非 rowkey的多维查询需求。如在基于位置的服务中，我们经常需要针对某个对象的经度、纬度、时间等属性进行多维查询；在图片共享服务中，我们可以对图片的拍摄时间、拍摄地点、图片主题等属性进行查询；在电子商务网站中，商品的数量往往达到数十亿甚至上百亿，并且每件商品都有几十个甚至上百个属性，如名称、类别、价格、上架时间等。用户往往需要从多个角度对商品进行查询，从而对所要购买的商品有更加全面深入的了解。
　　目前云数据管理系统在数据查询方面的局限性限制了其在众多领域的广泛应用。索引是实现多维查询的一个有效方案，因此目前已有很多学者、公司针对云数据管理中的索引技术开展了大量研究工作，并提出了一系列有价值的解决方案。如新加坡国立大学的 epiC项目组创新性地提出了双层索引框架，并在此基础上给出了一系列解决方案；华为技术有限公司基于 HBase的 Coprocessor技术设计了新的二级索引方案，大大提高了查询的效率。本节主要对云数据管理索引技术的相关工作进行深入调研，分析各自的优点及缺点；昀后指出了在云计算环境下针对大数据索引技术的若干挑战性问题。
　　2.2.1 云数据管理索引技术研究概述
　　云数据管理是指以云计算技术为基础，针对大规模数据的分布式、可扩展的数据管理技术。与传统数据管理(以关系型数据库管理为主)相比，在数据规模、数据对象、系统结构等方面都存在不同之处，并各有优劣，详细对比见表2.1。
　　表2.1 云数据管理与传统数据管理
　　为了丰富云数据管理系统的查询功能，提高数据查询和处理的效率，很多学者开展了云数据管理系统中索引技术的研究工作，并提出了很多有价值的实现方案。我们对各种索引方案的索引结构、实现方式、优缺点进行了深入分

目录
前言
第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