我有一个很大的用户和他们喜欢的项目的稀疏矩阵（按照 1M 用户和 100K 项目的顺序，稀疏度非常低）。我正在探索可以对其执行 kNN 搜索的方法。鉴于我的数据集的大小和我执行的一些初始测试，我的假设是我将使用的方法需要是并行的或分布式的。所以我正在考虑两类可能的解决方案：一类在单个多核机器上可用（或以相当简单的方式实现），另一类在 Spark 集群上，即作为 MapReduce 程序。以下是我考虑的三个广泛的想法：
对于我可以解决此问题的其他可能方式，我将不胜感激。
我希望以下资源可以为您提供解决问题的更多想法：
1) 研究论文《Efficient K-Nearest Neighbor Join Algorithms for High Dimensional Sparse Data》：http ://arxiv.org/abs/1011.2807
2）课堂项目论文《基于协同过滤的推荐系统》（斯坦福大学）：http ://cs229.stanford.edu/proj2008/Wen-RecommendationSystemBasedOnCollaborativeFiltering.pdf
3) Netflix 奖竞赛项目（基于k-NN）：http ://cs.carleton.edu/cs_comps/0910/netflixprize/final_results/knn/index.html
4) 研究论文“Hubs in Space：Popular Nearest Neighbors in High-Dimensional Data”关于维度诅咒及其与机器学习的关系，以及k-NN 算法，特别是：http: //jmlr.org /papers/volume11/radovanovic10a/radovanovic10a.pdf
5)稀疏 k-NN 分类软件（免费，但似乎不是开源的——可能与作者澄清）：http ://www.autonlab.org/autonweb/10408.html
6) StackOverflow上的几个讨论线程：
Python，这个指的是R生态系统）7）关注GraphLab，一个开源的机器学习并行框架（http://select.cs.cmu.edu/code/graphlab），通过模型支持并行聚类： http://select.cs.cmu。 edu/code/graphlab/clustering.htmlMapReduce
您还可以在 Data Science StackExchange 上查看我关于稀疏回归的答案，以获取相关R包和CRAN Task View页面的链接：https ://datascience.stackexchange.com/a/918/2452 。
如果您正在研究协同过滤，您应该将问题提出为低秩矩阵近似，其中两个用户都是项目共同嵌入到相同的低维空间中。相似性搜索会简单得多。正如你所建议的，我建议使用 LSH。另一个尚未提及的有效降维途径是随机投影。
您应该使用：PySparNN，这是 Facebook 最近在 python 中实现的一个非常快的实现。它也很容易使用。