我最近一直在定期做类似的程序。如果您处理大量文件，它并不快，并且需要相当大的硬盘空间。作为说明，我使用的数据具有更少的“功能”，更多的“用户”，我使用 perl 来处理它。

首先，我不建议将数据作为单个矩阵存储在一起，因为大多数程序（当然是 R）将无法处理它。如果您将每个用户存储为单独的文件（.txt 或任何其他更适合您的格式），那么您可以单独访问它们，即使使用 R。

然后，当一个新文档出现时，您必须在两个长度为 1000 万的向量之间进行 100,000 次比较。

这是 R 中的一个示例，其中包含两个长度为 10,000,000 的随机二进制向量。

x=as.numeric(rnorm(10000000)<0)

y=as.numeric(rnorm(10000000)<0)

sim = crossprod(x,y)/sqrt(crossprod(x)*crossprod(y))  

         [,1]
[1,] 0.4999211

由于本例中的两个向量是随机的 0,1 向量，因此它们的余弦相似度为 0.5。这个相似度（余弦 sim）计算花了不到一秒钟的时间，而我没有尝试对其进行优化。

要查看您的过程需要多长时间，您可以将此代码循环 100,000 次迭代，并将每个相似性结果存储到包含其所有匹配项的结果向量中。我用 1000 次迭代尝试了上面的代码，大约花了 70 秒。

您还可以插入所需的任何相似性度量。它在计算时间方面当然是可行的，但如果您需要更快地完成它，您可能需要优化它。希望这能让您了解计算可能需要什么。

你说的是信息检索的“向量空间模型”。Wikipedia 列出了一些对此有帮助的程序——我最熟悉的是 Lucene。

本页描述了他们的算法。要点是 1）你可以反转你的索引，2）你可以并行查看索引，3）你可以限制在顶部$k$. 所有这些都给你一个很好的加速。

您可以尝试按每行中“1”的总数（向量长度）对数据进行排序。当您获得新用户时，这将为您提供开始搜索的空间。例如，如果新用户的长度为 1342，您可以检查所有长度为正负 500 的条目。如果数据已排序，则可以有效地执行此操作。显然，这需要预先投入计算时间来对数据进行预排序。

最好的解决方案可能取决于您拥有的数据的特殊功能（您提到数据是稀疏的，因此您应该尝试以某种方式利用它）。如果两个向量的长度差异与它们之间的距离相关（例如汉明距离），我的回答将是有效的。您可以通过制作一个简单的散点图来检查数据的随机样本是否属实。

一般来说，最好的办法是确定一些标量函数，它可以很好地预测两个条目的相似程度，然后按该函数对数据进行排序，然后在给定新条目时在本地搜索。我的第一个猜测是尝试将向量长度作为该函数，但是您很有可能通过处理数据找到更好的函数。

有许多非欧式距离度量，其中一些专门用于二进制数据。两个距离度量是：1）简单匹配系数；2) 杰卡德系数。他们有一些不同的优点和缺点。在简单匹配系数中，相互不存在和存在有助于相似性，尽管 Jaccard 系数有利于关注相互存在。

如果需要，您可以更具体地查找这些度量（简单匹配和 Jaccard 总结如下：http: //stat.ethz.ch/education/semesters/ss2012/ams/slides/v4.2.pdf）

如果您使用 R，则基本包中的函数“dist”具有简单匹配系数（称为“二进制对称”），包“vegan”中的命令“vegdist”具有 Jaccard 索引。

（编辑）：我刚刚发现了一些东西，根据您的硬件，它可能会产生一些好处。如果你有一个 NVIDIA 多核 GPU（这是相当常见的），包 'rpud' 有一个函数 rpuDist()，它使用 GPU 计算许多标准距离度量，并有很大的改进，如下所示：[http:// www.r-tutor.com/gpu-computing/clustering/distance-matrix] http://www.r-tutor.com/gpu-computing/clustering/distance-matrix 我还没有测试过，并且有一个数据集您的尺寸可能还有其他瓶颈，但可能值得一试。此外，这个和另一个包（gputools）似乎只在 Linux 上可用，所以这是另一个限制......

希望有帮助！