Best bin first es un algoritmo de búsqueda que está 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 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 del árbol kd
- Los contenedores se examinan en orden creciente de distancia desde el punto de consulta. La distancia a un contenedor se define como una distancia mínima a cualquier punto de su límite. Esto se implementa con cola de prioridad. [2]
- Busque un número fijo de candidatos más cercanos y deténgase.
- Es típica una aceleración de dos órdenes de magnitud.
Referencias
- ^ Beis, J .; Lowe, DG (1997). Indización de formas mediante la búsqueda aproximada del vecino más cercano en espacios de gran dimensión . Conferencia sobre Visión por Computador y Reconocimiento de Patrones. Puerto Rico. págs. 1000–1006. CiteSeerX 10.1.1.23.9493 .
- ^ Indexación de formas mediante la búsqueda aproximada del vecino más cercano en espacios de alta dimensión, págs. 4-5