se han propuesto varias soluciones al problema NNS. La calidad y utilidad de los algoritmos están determinadas por la complejidad temporal de las consultas, así como la complejidad espacial de cualquier estructura de datos de búsqueda que deba mantenerse. La observación informal generalmente conocida como la maldición de la dimensionalidad establece que no hay una solución exacta de propósito general para NNS en el espacio euclidiano de alta dimensión utilizando el preprocesamiento polinómico y el tiempo de búsqueda polilogarítmico.,

métodos Exactosedit

búsqueda Linearedit

La solución más sencilla para el problema NNS es calcular la distancia desde el punto de consulta a cualquier otro punto de la base de datos, manteniendo un seguimiento de la «mejor hasta ahora». Este algoritmo, a veces referido como el enfoque ingenuo, tiene un tiempo de ejecución de O (dN), donde N es la cardinalidad de S y d es la dimensionalidad de M. no hay estructuras de datos de búsqueda para mantener, por lo que la búsqueda lineal no tiene complejidad de espacio más allá del almacenamiento de la base de datos., La búsqueda ingenua puede, en promedio, superar los enfoques de partición de espacios en espacios de dimensiones más altas.

space partitioningEdit

desde la década de 1970, la metodología branch y bound se ha aplicado al problema. En el caso del espacio euclidiano, este enfoque abarca el índice espacial o los métodos de acceso espacial. Se han desarrollado varios métodos de partición de espacios para resolver el problema NNS. Quizás el más simple es el árbol k-d, que iterativamente divide el espacio de búsqueda en dos regiones que contienen la mitad de los puntos de la región padre., Las consultas se realizan a través del árbol desde la raíz hasta una hoja evaluando el punto de consulta en cada división. Dependiendo de la distancia especificada en la consulta, las ramas vecinas que podrían contener hits también pueden necesitar ser evaluadas. Para el tiempo de consulta de dimensión constante, la complejidad promedio es O(log N) en el caso de puntos distribuidos aleatoriamente, la complejidad del peor caso es O(kN^(1-1/k))alternativamente, la estructura de datos r-tree fue diseñada para soportar la búsqueda de vecinos más cercanos en contexto dinámico, ya que tiene algoritmos eficientes para inserciones y eliminaciones como el árbol R*., Los árboles R pueden producir vecinos más cercanos no solo para la distancia euclidiana, sino que también se pueden usar con otras distancias.

en el caso del espacio métrico general, el enfoque de ramificación y encuadernación se conoce como enfoque de árbol métrico. Ejemplos particulares incluyen los métodos VP-tree y BK-tree.

Usando un conjunto de puntos tomados de un espacio tridimensional y puestos en un árbol BSP, y dado un punto de consulta tomado del mismo espacio, una posible solución al problema de encontrar el punto de nube de punto más cercano al punto de consulta se da en la siguiente descripción de un algoritmo., (Estrictamente hablando, tal punto no puede existir, porque puede no ser único. Pero en la práctica, por lo general solo nos importa encontrar cualquiera de los subconjuntos de todos los puntos de nube de puntos que existen a la distancia más corta a un punto de consulta dado.) La idea es, para cada ramificación del árbol, adivinar que el punto más cercano en la nube reside en el medio espacio que contiene el punto de consulta. Este puede no ser el caso, pero es una buena heurística., Después de haber pasado recursivamente por todo el problema de resolver el problema para el medio espacio adivinado, ahora compare la distancia devuelta por este resultado con la distancia más corta desde el punto de consulta hasta el plano de partición. Esta última distancia es la que existe entre el punto de consulta y el punto más cercano posible que podría existir en el medio espacio no buscado. Si esta distancia es mayor que la devuelta en el resultado anterior, entonces claramente no hay necesidad de buscar el otro medio espacio., Si hay tal necesidad, entonces debe pasar por la molestia de resolver el problema para el otro espacio de la mitad, y luego comparar su resultado con el resultado anterior, y luego devolver el resultado adecuado. El rendimiento de este algoritmo está más cerca del tiempo logarítmico que el tiempo lineal cuando el punto de consulta está cerca de la nube, porque como la distancia entre el punto de consulta y el punto más cercano-punto de nube 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óneditar

un algoritmo aproximado de búsqueda de vecinos más cercanos puede devolver puntos, cuya distancia desde la consulta es a lo sumo C {\displaystyle C} veces la distancia desde la consulta a sus puntos más cercanos. El atractivo de este enfoque es que, en muchos casos, un vecino aproximado más cercano es casi tan bueno como el exacto. En particular, si la medida de distancia captura con precisión la noción de calidad del usuario, entonces las pequeñas diferencias en la distancia no deberían importar.,

búsqueda codiciosa en grafos de vecindad cercanidadeditar

los métodos se basan en el recorrido codicioso en grafos de vecindad cercanidad G ( V , E ) {\displaystyle G(V,E)} en el que cada punto x i ∈ s {\displaystyle x_{i}\in s} está asociado únicamente con el vértice v i ∈ V {\displaystyle V_{I}\In V} . La búsqueda de los vecinos más cercanos a una consulta q en el conjunto S toma la forma de buscar el vértice en el gráfico G ( V , E ) {\displaystyle G(V,E)} .,El algoritmo básico-búsqueda codiciosa-funciona de la siguiente manera: la búsqueda comienza desde un vértice de punto de entrada v I ∈ V {\displaystyle v_{I}\In V} calculando las distancias desde la consulta q A cada vértice de su vecindario { v j: (v i , v j ) ∈ e } {\displaystyle \{V_{j}: (v_{i},v_{j})\in E\}} , 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 que existe entre la consulta y el elemento actual, entonces el algoritmo se mueve al vértice seleccionado, y 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 un vértice que esté más cerca de la consulta que el vértice en sí.

la idea de los gráficos de proximidad de vecindad fue explotada en múltiples publicaciones, incluyendo el artículo seminal de Arya y Mount, en el sistema VoroNet para el plano, en el sistema RayNet para el E n {\displaystyle \mathbb {E} ^{n}} , y en los algoritmos Metrized Small World y hnsw para el caso general de espacios con una función de distancia., Estas obras fueron precedidas por un artículo pionero de Toussaint, en el que introdujo el concepto de un gráfico de vecindad relativa.

hashing sensible a la Localidadeditar

el hashing 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 en los puntos. Los puntos que están cerca unos de otros bajo la métrica elegida se asignan al mismo cubo con alta probabilidad.,

búsqueda de vecinos más cercanos en espacios con dimensiones intrínsecaseditar

el árbol de cubierta tiene un límite teórico que se basa en la constante de duplicación del conjunto de datos. El límite en el tiempo de búsqueda es O (C12 log n) donde c es la constante de expansión del conjunto de datos.

búsqueda radial Proyectadaeditar

en el caso especial donde los datos son un mapa 3D denso de puntos geométricos, la geometría de proyección de la técnica de detección se puede utilizar para simplificar drásticamente el problema de búsqueda.,Este enfoque requiere que los datos 3D estén organizados por una proyección a una cuadrícula bidimensional y asume que los datos son espacialmente suaves a través de las celdas de la cuadrícula vecinas con la excepción de los límites de los objetos.Estas suposiciones son válidas cuando se trata de datos de sensores 3D en aplicaciones como topografía, robótica y visión estéreo, pero pueden no ser válidas para datos no organizados en general.In práctica esta técnica tiene un tiempo promedio de búsqueda de O(1) U O (K) para el problema K-nearest neighbor cuando se aplica a los datos de visión estéreo del mundo real.,

archivos de aproximación de Vectoreseditar

en espacios de alta dimensión, las estructuras de indexación de árboles se vuelven inútiles porque un porcentaje creciente de los nodos necesita ser examinado de todos modos. Para acelerar la búsqueda lineal, se utiliza una versión comprimida de los vectores de entidades almacenados en RAM para prefiltro de los conjuntos de datos en una primera ejecución. Los candidatos finales se determinan en una segunda etapa utilizando los datos sin comprimir del disco para el cálculo de la distancia.,

búsqueda basada en compresión/clustereditar

el enfoque VA-file es un caso especial de una búsqueda basada en compresión, donde cada componente de entidad se comprime de manera uniforme e independiente. La técnica de compresión óptima en espacios multidimensionales es la cuantización vectorial (VQ), implementada a través de clustering. La base de datos está agrupada y se recuperan los clústeres más «prometedores». Se han observado enormes ganancias sobre el archivo VA, los índices basados en árboles y el escaneo secuencial. También tenga en cuenta los paralelos entre clustering y LSH.