论文

https://www.cs.princeton.edu/cass/papers/www11.pdf

作者拟解决的主要问题

K近邻图的构建在很多基于Web的应用上是一个重要的操作，比如协同过滤（基于用户的邻居作推荐）、相似性搜索等。一个有效地构建方法将使K近邻图的应用更加广泛。

暴力构建K近邻图的时间复杂度为O ( n 2 ) O(n^2)O(n 2 )，为了能更高效的构建K近邻图，现存的工作扩展性都不太好，而且一般都特定于具体的相似性度量。

有效的K近邻图构建仍然是一个开放的问题，解决该问题的已知方案中没有一个是通用、有效和可扩展的。因此，本文提出了NN-Descent方法，该方法具有以下优点：

1. 通用。适用于任意的相似性度量准则。
2. 可扩展。随着数据集尺寸的增加，Recall仅有很小的下降。由于对每一个数据点的局部信息进行 操作，因此适用于分布式计算环境（MapReduce）.
3. 节省空间。整个构建过程仅涉及到一种数据结构——近邻图。
4. 快速、精确。百分之几的相似性比较便可实现90%以上的召回率。
5. 容易实施。主要代码不超过200行（C++）。

论文主要研究内容

如何有效地构建一个K近邻图，具体如下：

1. 适用任意相似性度量的K近邻图构建方法。
2. 在较短的时间内快速构建K近邻图的方法。
3. 构建一个在其上能快速、精确执行搜索的K近邻图。
4. 适用于MapReduce框架的K近邻图构建方案。

理论