Un algorithme pour trouver les meilleures correspondances en temps logarithmique attendu

Un algorithme et une structure de données sont présentés pour rechercher dans un fichier contenant N enregistrements, chacun décrit par k clés à valeurs réelles, les m correspondances les plus proches ou voisins les plus proches d'un enregistrement de requête donné. Le calcul requis pour organiser le fichier est proportionnel à kNlogN. Le nombre attendu d'enregistrements examinés à chaque recherche est indépendant de la taille du fichier. Le calcul attendu pour effectuer chaque recherche est proportionnel à logN. Des preuves empiriques suggèrent que, à l'exception des fichiers très petits, cet algorithme est considérablement plus rapide que d'autres méthodes.