本书是在作者近十年进行数据库理论与系统研究的基础上撰写的。书中将系统阐述和分析度量空间下多源异构（大）数据的索引、查询以及交互等问题，以有效解决度量空间数据管理问题。

度量空间数据管理
高云君 陈璐 编著

随着计算机、互联网、通信以及定位技术的快速发展，人们获取、存储和传输数据的能力日益增强。“传感器+互联网”形成的“数据海”融入通信、感知、计算、控制等系统中，不仅量大，而且涉及人类生活和生产的各个方面：文档、通信、新闻、电子邮件和网页上涌现的文本数据；基于位置的服务中产生的时空数据；科研机构、政府机关和企业运行过程中累积的医学、生物、气象、商业、地质数据；各类遥感、测绘、监控设备实时产生的流媒体数据；在线收集的自然环境和社会生活中的传感器数据等。1998年图灵奖获得者吉姆·格雷曾经断言，现在每18个月新增的数据量等于有史以来数据量之和[1]。继人力、资本之后，数据成为一种新的非物质生产要素，是支撑科学研究和各类应用服务不可或缺的战略资源[2]。2008年9月《自然》发表了名为 “Big Data: Science in the Petabyte Era” 的专刊，“大数据” 一词开始被广泛传播。
随着数据规模的不断增长，系统资源消耗量日益增大，系统运行效率显著降低。在大数据时代，当前相关技术很难支撑人们对各类大数据进行复杂而多样的智能处理需求，“数据在，找不到”的问题日益严重[1]。中国计算机学会大数据专家委员会发布的《中国大数据技术与产业发展白皮书》明确指出，大数据相关的索引和查询技术作为大数据的主要入口之一变得尤为重要。现有的（空间）索引和查询处理技术大多关注欧氏空间，并用欧氏距离来度量对象之间的邻近关系。但在许多实际应用（如地理信息系统、模式识别、生物计算、多媒体检索等）中，各类复杂对象（如图像、文档、基因序列等）不能使用多维向量表示，且对象之间的邻近关系并不能用欧氏距离度量，而需要用其他距离度量方式（如最短路径、编辑距离等）来衡量。因此，如何构建一个通用模型以规范表达各类数据是大数据管理的一大挑战。为此，需要借助度量空间。
本书的内容和组织结构
本书着重介绍度量空间数据管理技术，主要包括度量空间索引、度量空间查询和度量空间查询可用性。本书共分为6章，具体如下：
第1章阐述数据管理和度量空间的基本概念，并指出度量空间索引和查询存在的问题。
第2章介绍高效的度量空间索引，包括确定度量数据索引和不确定度量数据索引。
第3章介绍集中式度量空间查询处理技术，包括度量全k最近邻查询和度量k最近对查询。
第4章介绍分布式度量空间查询处理技术，并提出基于MapReduce的度量相似连接处理算法。
第5章介绍度量空间查询可用性分析技术，引入并解决了度量概率区域查询上的Whynot问题。
第6章介绍一个集成已有的度量空间索引与查询处理技术的分布式社交图像检索与推荐系统。
致谢
本书是作者在多年研究成果的基础上总结整理而成的。首先感谢国家自然科学基金委和国家973计划的一贯支持，作者在近六年研究中得到了如下项目的资助：
2011~2013年，国家自然科学青年科学基金项目“障碍环境下的反最近邻查询处理技术研究”，编号：61003049。
2014~2017年，国家自然科学基金面上项目“度量空间下的k最近对查询及变体处理研究”，编号：61379033。
2015~2019年，国家重点基础研究发展计划（973计划）子课题项目“城市多模态数据的语义计算与融合”，编号：2015CB352502。
2016~2018年，国家优秀青年科学基金项目“数据库理论与系统（缺失数据处理理论与方法研究）”，编号：61522208。
2017~2020年，NSFC浙江两化融合联合基金项目“城市多源异构数据的关联建模与可视分析”，编号：U1609217。
本书凝聚了实验室的集体智慧。特别感谢实验室的博士生柳晴、杨克宇和葛丛丛以及硕士生李信晗、邢郅豪、张远亮和仲启露。
本书可以作为普通高校计算机和信息技术相关专业的数据库与大数据管理研究生课程的教材，也可供从事计算机相关专业的技术人员和学者作为参考书。
感谢机械工业出版社华章分社的编辑，他们在全书的校对和编辑出版过程中付出了巨大的努力。
因作者水平有限，书中错误在所难免，恳请读者批评指正。

计算机\数据库

丛书简介
本套丛书是面向新形势下的大数据技术发展对人才培养提出的挑战以及知识
更新的需求而策划组织的，旨在为学术研究和人才培养提供可供参考的“基石”。
丛书内容涵盖大数据管理的理论、方法、技术等诸多方面，选题面向技术热点，
弥补现有知识体系的漏洞和不足，力图为现有的数据管理知识查漏补缺，聚少成多，
最终形成适应大数据技术发展和人才培养的知识体系和教材基础。丛书主编是中国人民大学孟小峰教授。

丛书前言
前言
第1章基本概念
11数据管理
111关系型数据管理系统
112空间数据管理系统
113下一代数据管理系统
12度量空间
13存在的问题
第2章度量空间索引
21度量空间索引综述
211基于划分的索引方法
212基于支枢点的索引方法
213混合索引方法
214国内度量空间索引研究
215分析与讨论
22确定度量数据索引
221索引构建框架
222支枢点选择方法
223SPB树
224基于SPB树的度量区域查询
225基于SPB树的度量k最近邻查询
226分析与讨论
227实验评估
23不确定度量数据索引
231研究动机
232数据表达模型
233UPB树和UPB森林
234支枢点选择方法
235基于UPB树的度量概率区域查询
236基于UPB森林的度量概率区域查询
237分析与讨论
238实验评估
24本章小结
第3章集中式度量空间查询
31集中式度量空间查询综述
311集中式度量相似查询处理技术
312集中式度量反k最近邻查询处理技术
313集中式度量相似连接处理技术
314集中式度量全k最近邻查询处理技术
315集中式度量k最近对查询处理技术
316集中式度量Skyline查询处理技术
317国内集中式度量空间查询研究
318分析与讨论
32度量全k最近邻查询
321研究动机
322问题陈述
323剪枝策略
324查询算法
325分析与讨论
326实验评估
33度量k最近对查询
331研究动机
332问题陈述
333剪枝策略
334查询算法
335分析与讨论
336实验评估
34本章小结
第4章分布式度量空间查询
41分布式度量空间查询综述
411分布式相似连接处理技术
412分布式全k最近邻查询处理技术
413分布式Skyline查询处理技术
414其他分布式查询处理技术
415国内分布式海量数据查询研究
42基于MapReduce的度量相似连接
421研究动机
422基于MapReduce的算法框架
423基于聚簇的划分方法
424基于KD树的划分方法
425Reduce阶段
426实验评估
43本章小结
第5章度量空间查询可用性分析
51查询结果可用性分析综述
511Why与Whynot问题
512Causality与Responsibility问题
513Whyfew与Whymany问题
52度量概率区域查询上的Whynot问题
521研究动机
522问题陈述
523处理算法
524分析与讨论
525实验评估
53本章小结
第6章社交图像检索与推荐系统
61研究动机
62数据模型与查询
63系统框架与实现
631系统框架
632社交图像索引
633查询处理
64系统演示
65本章小结
参考文献