La búsqueda del vecino más cercano (NNS, por sus siglas en inglés, Nearest Neighbor Search), como una forma de búsqueda por proximidad, es el problema de optimización que consiste en encontrar el punto en un conjunto dado que sea el más cercano (o más similar) a un punto dado. La cercanía se expresa típicamente en términos de una función de disimilitud: cuanto menos similares sean los objetos, mayores serán los valores de la función.

Formalmente, el problema de búsqueda del vecino más cercano (NN) se define de la siguiente manera: dado un conjunto de puntos en un espacio y un punto de consulta , encontrar en el punto más cercano a . Donald Knuth, en el volumen 3 de su obra The Art of Computer Programming (1973), lo denominó el problema de la oficina de correos, en referencia a una aplicación para asignar a una residencia la oficina de correos más cercana. Una generalización directa de este problema es una búsqueda -NN, donde se necesita encontrar los puntos más cercanos.

Lo más común es que sea un espacio métrico y la disimilitud se exprese como una métrica de distancia, que es simétrica y satisface la desigualdad triangular. Aún más común es que sea un espacio vectorial de dimensión , donde la disimilitud se mide usando la distancia euclídea, la geometría del taxista u otra métrica de distancia. Sin embargo, la función de disimilitud puede ser arbitraria. Un ejemplo es la divergencia de Bregman asimétrica, para la que no se cumple la desigualdad triangular.

Aplicaciones El problema de búsqueda del vecino más cercano surge en numerosos campos de aplicación, entre ellos: Reconocimiento de patrones, en particular para el reconocimiento óptico de caracteres Clasificación estadística (véase k vecinos más próximos) Visión artificial, para el registro de nubes de puntosQiu, Deyuan, Stefan May, and Andreas Nüchter. "GPU-accelerated nearest neighbor search for 3D registration." International conference on computer vision systems. Springer, Berlin, Heidelberg, 2009. Geometría computacional (véase el problema del par de puntos más cercanos) Criptoanálisis, para el problema del retículoBecker, Ducas, Gama, and Laarhoven. "New directions in nearest neighbor searching with applications to lattice sieving." Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms (pp. 10-24). Society for Industrial and Applied Mathematics. Bases de datos, como para la consulta de imágenes mediante ejemplo Teoría de códigos (véase decodificación de máxima verosimilitud) Búsqueda semántica Base de datos de vectores, donde se utiliza la búsqueda del vecino más cercano sobre incrustaciones para recuperar registros semánticamente similares Sistemas de generación aumentada por recuperación, donde se utiliza la recuperación del vecino más cercano sobre incrustaciones para obtener pasajes o documentos candidatos antes de la generación Compresión de datos (véase MPEG-2 estándar) Robótica, en la detección de objetos Sistemas de recomendación (véase filtrado colaborativo) Mercadeo digital (véase publicidad contextual y focalización conductual) Secuenciación del ADN Correctores ortográficos, con sugerencias de ortografía correcta Detección de plagios Puntuación de similitud, para predecir las trayectorias de deportistas profesionales Análisis de grupos, para la asignación de un conjunto de observaciones a subconjuntos (denominados clústeres) de modo que las observaciones dentro del mismo clúster sean similares en algún sentido, generalmente basándose en la distancia euclídea Similitud química Planificación de movimiento basada en muestreo

Métodos Se han propuesto diversas soluciones al problema de la búsqueda de redes neuronales (NNS). La calidad y utilidad de los algoritmos están determinadas por la complejidad temporal de las consultas, así como por la complejidad espacial de las estructuras de datos de búsqueda que deben mantenerse. La observación informal, generalmente denominada maldición de la dimensión, indica que no existe una solución exacta de propósito general para la búsqueda de NNS en espacios euclídeos de alta dimensión utilizando preprocesamiento polinomial y tiempo de búsqueda polilogarítmico.

Métodos exactos

Búsqueda lineal La solución más simple al problema de NNS consiste en calcular la distancia desde el punto de consulta a todos los demás puntos de la base de datos, registrando el "mejor resultado hasta el momento". Este algoritmo, a veces denominado enfoque ingenuo, tiene una complejidad temporal de O(dN), donde N es la cardinalidad de S, y d es la dimensión de S. No se requieren estructuras de datos de búsqueda, por lo que la búsqueda lineal no tiene complejidad espacial más allá del almacenamiento de la base de datos. La búsqueda ingenua puede, en promedio, superar a los enfoques de partición espacial en espacios de mayor dimensión.

Para comparar distancias, no se requiere la distancia absoluta, solo la relativa. En sistemas de coordenadas geométricas, el cálculo de la distancia se puede acelerar considerablemente omitiendo la raíz cuadrada. Aun así, la comparación de distancias dará resultados idénticos.

Particionamiento espacial Desde la década de 1970, la metodología de ramificación y poda se ha aplicado al problema. En el caso del espacio euclídeo, este enfoque abarca los métodos de base de datos espacial o de acceso espacial. Se han desarrollado varios métodos de particionado del espacio para resolver el problema NNS. Quizás el más simple sea el árbol kd, que biseca iterativamente el espacio de búsqueda en dos regiones que contienen la mitad de los puntos de la región original. Las consultas se realizan recorriendo el árbol desde la raíz hasta una hoja, evaluando el punto de consulta en cada bifurcación. Dependiendo de la distancia especificada en la consulta, también puede ser necesario evaluar las ramas vecinas que podrían contener coincidencias. Para un tiempo de consulta de dimensión constante, la complejidad promedio es O(log N) En el caso de puntos distribuidos aleatoriamente, la complejidad en el peor de los casos es O(kN^(1-1/k))

Alternativamente, la estructura de datos árbol-R se diseñó para admitir la búsqueda del vecino más cercano en un contexto dinámico, ya que cuenta con algoritmos eficientes para inserciones y eliminaciones, como árbol R*. Los árboles R pueden proporcionar vecinos más cercanos no solo para la distancia euclídea, sino que también pueden usarse con otras distancias.

En el caso de un espacio métrico general, el enfoque de ramificación y acotación se conoce como el enfoque del árbol métrico. Algunos ejemplos particulares incluyen los métodos árbol vp y árbol BK.

Utilizando un conjunto de puntos extraídos de un espacio tridimensional y colocados en una nube de puntos mediante un árbol binario, y dado un punto de consulta extraído del mismo espacio, se presenta una posible solución al problema de encontrar el punto de la nube de puntos más cercano al punto de consulta en la siguiente descripción de un algoritmo. Estrictamente hablando, tal punto podría no existir, ya que podría no ser único. Sin embargo, en la práctica, generalmente solo interesa encontrar cualquiera de los puntos de la nube de puntos que se encuentran a la distancia más corta de un punto de consulta dado. La idea es, para cada ramificación del árbol, suponer que el punto más cercano en la nube reside en el semiplano que contiene el punto de consulta. Esto podría no ser así, pero es una buena heurística. Después de haber realizado recursivamente todos los cálculos para resolver el problema en el semiplano supuesto, ahora se compara la distancia devuelta por este resultado con la distancia más corta desde el punto de consulta al plano de partición. Esta última distancia es la que existe entre el punto de consulta y el punto más cercano posible en el semiplano no explorado. Si esta distancia es mayor que la obtenida en el resultado anterior, entonces claramente no es necesario explorar el otro semiplano. Si existe tal necesidad, entonces se debe resolver el problema para el otro semiplano, comparar su resultado con el anterior y, finalmente, devolver el resultado correcto. El rendimiento de este algoritmo se aproxima más al tiempo logarítmico que al lineal cuando el punto de consulta está cerca de la nube de puntos, ya que, a medida que la distancia entre el punto de consulta y el punto más cercano de la nube de puntos se acerca a cero, el algoritmo solo necesita realizar una búsqueda utilizando el punto de consulta como clave para obtener el resultado correcto.

Métodos de aproximación Un algoritmo de búsqueda aproximada del vecino más cercano puede devolver puntos cuya distancia desde la consulta sea como máximo veces la distancia desde la consulta a sus puntos más cercanos. La ventaja de este enfoque es que, en muchos casos, un vecino más cercano aproximado es casi tan bueno como uno exacto. En particular, si la medida de distancia refleja con precisión la noción de calidad fijada por el usuario, entonces las pequeñas diferencias en la distancia no deberían importar.

Búsqueda voraz en grafos de vecindad de proximidad Los métodos de grafos de proximidad (como los grafos de mundo pequeño navegables y de pequeño mundo navegable jerarquizado o estratificado (HNSW)) se consideran el estado del arte actual para la búsqueda aproximada de vecinos más cercanos.

Los métodos se basan en el recorrido voraz en grafos de vecindad de proximidad , donde cada punto está asociado de forma única con el vértice . La búsqueda de los vecinos más cercanos a una consulta q en el conjunto S se realiza buscando el vértice en el grafo .

El algoritmo básico de búsqueda voraz funciona de la siguiente manera: la búsqueda comienza en un vértice de entrada calculando las distancias desde la consulta q a cada vértice de su vecindario , y luego encuentra un vértice con el valor de distancia mínimo. Si el valor de distancia entre la consulta y el vértice seleccionado es menor que el valor entre la consulta y el elemento actual, el algoritmo se mueve al vértice seleccionado, que se convierte en un nuevo punto de entrada. El algoritmo se detiene cuando alcanza un mínimo local: un vértice cuyo vecindario no contiene ningún vértice más cercano a la consulta que el propio vértice.

La idea de los grafos de vecindad de proximidad se explotó en múltiples publicaciones, incluyendo el artículo fundamental de Arya y Mount, en el sistema VoroNet para el plano, en el sistema RayNet para , y en los algoritmos Navigable Small World, Metrized Small World, y HNSW, para el caso general de espacios con una función de distancia. Estos trabajos fueron precedidos por un artículo pionero de Toussaint, en el que introdujo el concepto de grafo de "vecindario relativo".

Dispersión sensible a la localidad La dispersión sensible a la localidad (LSH) es una técnica para agrupar puntos en el espacio en "cubos", basados en alguna métrica de distancia que opera sobre los puntos. Los puntos cercanos entre sí, según la métrica elegida, se asignan al mismo grupo con alta probabilidad.

Búsqueda del vecino más cercano en espacios con dimensión intrínseca pequeña El árbol de recubrimiento tiene un límite teórico basado en el espacio doblante del conjunto de datos. El límite del tiempo de búsqueda es O(c12 log n), donde c es la constante de expansión del conjunto de datos.

Búsqueda radial proyectada En el caso especial de que los datos sean un mapa 3D denso de puntos geométricos, la geometría de proyección de la técnica de detección puede utilizarse para simplificar drásticamente el problema de búsqueda.