Um Algoritmo para Encontrar as Melhores Correspondências em Tempo Esperado Logarítmico

Um algoritmo e uma estrutura de dados são apresentados para a busca em um arquivo contendo N registros, cada um descrito por k chaves de valor real, para encontrar as m correspondências mais próximas ou vizinhos mais próximos de um registro de consulta dado. O cálculo necessário para organizar o arquivo é proporcional a kNlogN. O número esperado de registros examinados em cada busca é independente do tamanho do arquivo. O cálculo esperado para realizar cada busca é proporcional a logN. Evidências empíricas sugerem que, exceto para arquivos muito pequenos, este algoritmo é consideravelmente mais rápido que outros métodos.