基于Spark的高维数据相似性连接算法的研究与实现

摘要

高维数据的相似性连接是指在给定的具有较高维度的数据集中，根据要求的距离计算公式，计算出距离小于给定阈值的向量对。该操作在图像相似度匹配、文本聚类、朋友推荐中有着广泛的应用。但是随着信息技术的发展，数据量的急剧增加，高维数据的相似性连接面临许多挑战。因此，对高维数据的相似性连接的研究有助于提高相关应用领域的效率。通过对现有高维数据相似性连接技术的研究，我们发现很多算法都存在数据冗余、计算重复、占用资源较多等问题，同时实验的效果也不够理想。 为了解决以上问题，我们在本文中提出了自己的算法SAVD。其主要是将数据降维技术分段聚合表示(PAA)、符号化聚合表示(SAX)和垂直划分技术相结合。它的具体思想为首先将标准化向量进行PAA和SAX表示;其次对其进行垂直划分;然后通过使用本文提出的过滤方法处理垂直分区得到候选集;最后聚合各分区候选集并进行验证，找出所有满足距离要求的结果集。该方法解决了已有工作中存在的问题，提高了算法的执行效率。同时我们将算法进行了优化，提出了通过三角不等式比较来过滤掉不必要的向量间计算，这样可以极大的提高算法的执行效率和降低算法的复杂度。为了验证本文中提出的算法的效率，在实验部分分别用MapReduce和Spark框架对该算法进行了实现，并在公开的数据集上与已有的算法进行了对比验证。实验结果表明，本文中提出的方法比现有方法有更高的效率。 另外，针对现有使用场景中数据量持续增长的问题，我们将本文提出的算法SAVD在增量高维数据集中进行了拓展研究。首先将原始数据SAX降维处理后并垂直分区的中间运算结果存储到指定位置，然后对增量数据按相同的标准降维和垂直分区后与原始数据的中间输出合并运算，最后分别计算增量数据与原始数据集的相似性连接和计算增量数据与该数据集中的连接。实验证明，我们提出的方法要比直接使用相似性连接有更高的效率。

目录

声明

摘要

第一章绪论

1．1本文的研究背景及意义

1．2国内外的研究现状

1．2．1数据相似性连接分类

1．2．2一般数据相似性连接研究现状

1．2．3高维数据相似性连接研究现状

1．3目前存在的问题

1．4本文的主要研究内容

1．5本文的组织结构

第二章研究基础和相关技术

2．1大数据处理相关技术

2．1．1 Hadoop技术

2．1．2 Spark技术

2．1．3 Hadoop与Spark的比较

2．2高维数据相似性连接

2．2．1高维数据相似性连接定义

2．2．2高维数据相似性连接算法

2．3高维数据垂直划分技术

2．4本章小结

第三章高维数据相似性连接研究与实现

3．1基于Spark的SAVD算法研究和实现

3．1．1 SAVD算法原理

3．1．2 SAVD算法实现

3．2改进的SAVD算法I-SAVD算法研究和实现

3．2．1 I-SAVD算法原理

3．2．2 I-SAVD算法实现

3．3本章实验

3．3．1实验配置

3．3．2数据集

3．3．3实验及评估

3．4本章小结

第四章高维数据相似性连接的增量式计算方法研究与实现

4．1增量式高维数据连接原理

4．2增量式高维数据连接实现

4．3本章实验

4．4本章小结

第五章总结与展望

参考文献

发表论文和参加科研情况说明

致谢