Búsqueda aproximada del vecino más cercano (1+ε)

Caso especial del problema de búsqueda del vecino más cercano

La búsqueda del vecino más cercano aproximado (1+ ε ) es una variante del problema de búsqueda del vecino más cercano . Una solución para la búsqueda del vecino más cercano aproximado (1+ ε ) es un punto o varios puntos dentro de una distancia (1+ ε ) R desde un punto de consulta, donde R es la distancia entre el punto de consulta y su verdadero vecino más cercano. ^[1]

Las razones para aproximar la búsqueda del vecino más cercano incluyen los costos de espacio y tiempo de las soluciones exactas en espacios de alta dimensión (ver la maldición de la dimensionalidad ) y que en algunos dominios, encontrar un vecino más cercano aproximado es una solución aceptable.

Los enfoques para resolver la búsqueda del vecino más cercano aproximado (1+ ε ) incluyen árboles kd , ^[2] hash sensible a la localidad y búsqueda de fuerza bruta .

Referencias

1. Arya, Sunil; Mount, David M. (1993). "Consultas aproximadas de vecinos más próximos en dimensiones fijas". Actas del Cuarto Simposio Anual ACM-SIAM sobre Algoritmos Discretos . pp. 271–280. ISBN 978-0-89871-313-8.
2. Arya, Sunil; Mount, David M.; Netanyahu, Nathan; Silverman, Ruth; Wu, Angela Y. (1994). "Un algoritmo óptimo para la búsqueda aproximada del vecino más próximo en dimensiones fijas". Actas del quinto simposio anual ACM-SIAM sobre algoritmos discretos . págs. 573–582. ISBN 978-0-89871-329-9.