我们在Twitter的朋友已经为MLlib做了贡献，这篇文章使用了Twitter描述其开源贡献的材料，并得到了许可。相关的pull请求将在apachespark1.2中发布。介绍我们经常感兴趣的是寻找用户、标签和广告，它们彼此非常相似，因此它们可能会被推荐给用户和广告商。要做到这一点，我们必须考虑多对项目，并评估它们之间的"相似性"。我们称之为"所有对相似性"问题，有时也被称为"相似性联接"。我们开发了一种新的高效算法来解决相似性联接，称为"使用MapReduce的维度无关矩阵平方"，简称DIMSUM，这使得Twitter最昂贵的批处理计算效率提高了40%。为了更形式化地描述我们试图解决的问题，当给定稀疏向量数据集时，所有对相似性问题就是根据一个相似函数（如余弦相似性）和给定的相似度阈值来寻找所有相似的向量对。并不是所有的项对彼此都相似，然而一个朴素的算法将花费计算精力来考虑甚至那些不太相似的项对。考虑所有项目对的暴力方法很快就崩溃了，因为它的计算量是二次方的。例如，对于一百万个向量，不可能检查所有大约万亿个向量对，看它们是否超过相似性阈值。尽管如此，有一些聪明的采样技术可以将计算工作集中在那些超过相似阈值的对上，从而使问题变得可行。我们开发了DIMSUM抽样方案，将计算精力集中在那些高度相似的对上，从而使问题变得可行。直觉提高效率的主要原因是采样列中有许多非零且概率较低。另一方面，非零较少的列将以更高的概率进行采样。这种抽样方案可以证明准确地估计余弦相似性，因为那些有许多非零的列有更多的试验要包括在样本中，因此可以以较低的概率进行抽样。在Twitter工程博客上有对该算法的深入描述。实验我们在生产规模的广告数据集上运行DIMSUM。在6月下旬取代传统的余弦相似度计算后，我们观察到几个性能指标提高了40%，如下图所示。Spark的用法该算法在apachespark MLlib中可用作RowMatrix中的一种方法。这使其易于使用和访问：//输入和阈值的参数val文件名=参数（0）val阈值=args（1）.toDouble//加载并解析数据文件。val行=sc.TEXT文件（文件名）.map{line=>val值=线.分割（''）.map（\.toDouble）向量。密集（值）}val mat=新的行矩阵（行）//用蛮力完美地计算相似的列。val simsPerfect=材料柱相似性()//使用DIMSUM计算带有估计的相似列值模拟值=材料柱相似性（基本要求）下面是一个调用DIMSUM的示例。此功能将从Spark 1.2开始提供。有关DIMSUM算法的GigaOM文章中可以找到更多信息。免费试用Databricks。今天就开始吧