Best 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 dimensiones muy altas. El algoritmo se basa en una variante del algoritmo de búsqueda de árbol kd que hace posible 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 consultas y un vecino muy cercano en caso contrario. [1]
Diferencias con el árbol kd
- Los contenedores se analizan 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 la cola de prioridad . [2]
- Busque un número fijo de candidatos más cercanos y deténgase.
- Una aceleración de dos órdenes de magnitud es típica.
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 Computador 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 próximo en espacios de alta dimensión, págs. 4-5
