如果你想要开一家咖啡店，你或许会想问一个问题：附近最近的咖啡店在哪里？这个问题的答案可以帮你了解竞争对手的情况。这是计算机科学中广泛研究的“最近邻”搜索问题的一个例子。这个问题研究的是：在给定一个数据集合和一个新的数据点的情况下，在现有数据集合中，哪个点距离新的点最近？这个问题出现在很多日常情境中，例如基因组研究、图像搜索、歌曲推荐等。
与咖啡店这个例子不同的是，最近邻问题往往非常难解答。
问题的复杂性主要在于，对于不同类型的数据集，两点间距离的定义可能截然不同。我们已经完全习惯的一种定义距离的方式，就是在两点之间绘制直线，也就是我们通常所说的欧几里德距离。然而，在有些情况下，其他定义距离的方式更为合理。例如，在街道纵横如网格的大城市中，从一个地点到另一个地点的最短距离会是，横着向东走3公里，然后向北走4公里，而不是飞跃所有房屋的直线距离5公里。
这种强迫你转90度弯的定义方式就是所谓的曼哈顿距离。
国际象棋的棋盘上，“王”从一个位置走到另一个位置需要的最少步数，被称为切比雪夫距离，也叫棋盘距离。曼哈顿距离、欧几里德距离与切比雪夫距离，分别对应于p-范数距离中的1-范数、2-范数、无穷范数。除了从空间地理位置的角度来思考距离，还存在许多适用于其他特定类型问题的距离度量。
计算机科学中用“编辑距离”（Edit Distance）来量化比较两个字符串（例如英文单词）的差异程度。生物学家也常使用“编辑距离”，例如基因序列可被看作是A、T、C、G四个字母组成的字符串，编辑距离可用来量化比较两个基因组的相似度：两个基因序列之间的编辑距离，就是将一个序列转换成另一个序列过程中，所需的添加、删除、插入和替换的数量。
寻找最近邻的标准方法，是将现有数据划分成组。例如想象一下，你的数据是草地上绵羊的位置，将成群的绵羊圈起来，如果这时草地上来了一只新绵羊，它会落入哪个圈呢？新来绵羊的最近邻在很大概率上、甚至是必然的情况下，也会在那个圈里。然后重复这个过程，将这些圈再次划分成更小的圈，不断地对它们继续进行划分……最终，划分的圈子将只包含两个点：一个是原来就已存在的点，一个是新的点。而原来存在的点就是新点的最近邻。
多年来，计算机科学家已经提出了各种划分区域的算法。对于每个点仅由几个值定义的低维数据（如草地上绵羊的位置），算法会生成沃罗诺伊图（Voronoi diagram）来精确地求解最近邻问题。对于每个点可以由成百上千个值定义的更高维度的数据，沃罗诺伊图的计算量过大。因此，计算机科学家转而用一种被称为“局部敏感散列”（locality sensitive hashing，LSH）的算法来进行划分。
最近，五位计算机科学家组成的一个团队提出了一种全新的方法来解决最近邻问题。在相继发表的两篇论文中，他们阐述了解决复杂数据最近邻问题的第一个通用方法。论文的作者之一、麻省理工学院的计算机科学家、在开发最近邻问题算法方面很有影响力的人物Piotr Indyk说：“这是第一个使用单个算法捕捉到多种空间度量的成果。”
这项新的工作中，计算机科学家不再追寻特定的最近邻算法，而是退后一步，思考一个更广泛的问题：对于一个距离度量，是什么因素阻止了最近邻算法的存在？他们认为，这与寻找扩展图（expander graph）的最近邻问题有关，是一个非常困难的问题。扩展图是一种特定类型的图，它们由顶点和连接顶点的边组成，具有自己的距离度量。图上两点间的距离，是从一点到另一点需要经过的边的最小数目。
总的来说，新的论文首次重塑了对高维数据的最近邻搜索。计算机科学家不再需要为每一个特定的距离度量设计一个算法，现在，他们有了一个适合所有度量的最近邻算法。