Un algoritmo para encontrar las mejores coincidencias en tiempo esperado logarítmico

Se presenta un algoritmo y una estructura de datos para buscar en un archivo que contiene N registros, cada uno descrito por k claves de valor real, las m coincidencias más cercanas o vecinos más próximos a un registro de consulta dado. El cálculo requerido para organizar el archivo es proporcional a kNlogN. El número esperado de registros examinados en cada búsqueda es independiente del tamaño del archivo. El cálculo esperado para realizar cada búsqueda es proporcional a logN. Evidencia empírica sugiere que, excepto para archivos muy pequeños, este algoritmo es considerablemente más rápido que otros métodos.