Hispanopedia WikiBest bin first es un algoritmo de búsqueda diseñado para encontrar de manera eficiente una solución aproximada al problema de búsqueda del vecino más cercano en espacios de muy alta dimensión. El algoritmo se basa en una variante del algoritmo de búsqueda kd-tree , lo que permite la indexación de espacios de dimensiones superiores. Best bin first es un algoritmo aproximado que devuelve el vecino más cercano para una gran fracción de las consultas y un vecino muy cercano en caso contrario. [ 1 ]
Diferencias con el árbol kd
- Los contenedores se examinan en orden creciente de distancia desde el punto de consulta. La distancia a un contenedor se define como la distancia mínima a cualquier punto de su límite. Esto se implementa con una cola de prioridad . [ 2 ]
- Buscar un número fijo de candidatos cercanos y detenerse.
- Lo habitual es una aceleración de dos órdenes de magnitud.
Referencias
- ↑ Beis, J.; Lowe, DG (1997). Indexación de formas mediante búsqueda aproximada del vecino más cercano en espacios de alta dimensión . Conferencia sobre Visión por Computadora y Reconocimiento de Patrones. Puerto Rico. pp. 1000–1006 . CiteSeerX 10.1.1.23.9493 .
- ↑ Indexación de formas mediante búsqueda aproximada del vecino más cercano en espacios de alta dimensión, págs. 4-5
Categorías :
- Algoritmos de búsqueda
- Algoritmos y estructuras de datos básicos