最邻近搜索

最邻近搜索（NNS）又称为“最近点搜索”（Closest point search），是一个在尺度空间中寻找最近点的优化问题。问题描述如下：在尺度空间M中给定一个点集S和一个目标点q ∈ M，在S中找到距离q最近的点。很多情况下，M为多维的欧几里得空间，距离由欧几里得距离或曼哈顿距离决定。

高德纳在《计算机程序设计艺术》（1973）一书的第三章中称之为 邮局问题，即居民寻找离自己家最近的邮局。

最邻近搜索问题在很多领域中都有应用，包括：

模式识别，特别是光学字符识别 统计分类，参见KNN（k-nearest neighbor algorithm） 计算机视觉 数据库，如基于内容的图像检索 编码理论，见最大似然编码 数据压缩，见MPEG-2标准 向导系统 网络营销 DNA测序 拼写检查，建议正确拼写。 剽窃侦查 相似比分算法，用来推断运动员的职业表现。

方法

最邻近搜索问题有若干种解决方案，这些算法的优劣决定于他们求解的时间复杂度和用来查找的数据结构的空间复杂度。一种通常的说法表述为“尺度的限制”（curse of dimensionality），指对于在大维数的欧几里得空间里用最邻近搜索的话，无法找到多项式的算法和多对数的查找时间。