成小海

(天津工业大学 计算机科学与软件学院，天津 300387)

0 引 言

高维数据相似性连接不仅可以用于分类，而且还可以用于预测，在文本分类、聚类分析、预测分析、模式识别、图像处理等领域应用广泛。但高维数据相似性连接仍是一个非常具有挑战性的工作，主要有以下两个原因。首先，数据集的规模非常大(数百万或数十亿的对象)；其次，数据集的维数足够高(数千或数万)。因此不可能直接对数据集进行操作，必须借助有效的方法来降低数据集的维数，从而进行数据集间的运算[1]，其中用的最多的就是结合Hadoop框架[2-9]进行分布式运算。

近年来，有学者不断地对高维数据的相似性连接进行了研究和优化。例如，戴健等[7]整合MapReduce框架,提出了分布式网格概略化KNN joins(DSGMP-J)和基于MapReduce的voronoi diagram下的KNN joins(VDMP-J)；马友忠等[8]结合Hadoop集群的分布式特性和SAX的降维技术，提出了向量随机生成id的方式进行SAX转换，虽然可以起到分布式计算的效果，但在运算过程中由于复制多份数据和相同id向量的重复计算导致内存消耗较大;刘雪莉等[10]提出了实体数据库上相似性连接算法ES-joins，用于解决字符串模糊匹配的相似性连接问题；刘艳等[11]利用Δ-tree进行高维数据相似连接；周健雯等[12]使用R*树的自相似性连接。

由于Spark具有运算速度快、易用性好和通用性强等优点，并且可以高效地处理大规模数据集，因此文中采用基于Spark的相似性连接，对原有基于MapReduce的方法进行改进，优化其中的计算步骤，同时结合Spark强大的RDD算子，以提高计算速度。……