Comment puis-je trouver les valeurs de k-plus proches dans un espace à n dimensions?

Question

Je lis des kd-arbres mais ils sont inefficaces quand la dimensionalité de l'espace est élevée. J'ai une base de données de valeur et je veux trouver les valeurs qui sont dans une certaine distance de hamming de la requête. Par exemple, la base de données est une liste de nombres de 32 bits et je veux trouver tous les nombres qui diffèrent de la valeur de la requête de moins de 3 bits.

J'ai entendu quelque part à propos des arborescences MultiVariate Partition mais je n'ai pas trouvé de bonne référence. Je sais que min-Hash donne une bonne approximation, mieux que le mais je voudrais une réponse exacte.

Answer 1

La distance de Hamming est étroitement liée à levenshtein distance, et est similaire aux algorithmes utilisés pour la correction orthographique. Une méthode qui fonctionne est branch-and-bound recherche dans un trie. Cela prend du temps qui est exponentiel dans le lointain, pour une distance proche, jusqu'à être linéaire dans la taille du dictionnaire.

Si le dictionnaire est de mots binaires stockés dans une structure arborescente binaire, avec une distance stricte de Hamming, ici est un simple pseudo-code:

walk(trie, word, i, hit, budget){ 
    if (budget < 0 || i > word.length) return; 
    if (trie==NULL){ 
    if (i==word.length) print hit; 
    return; 
    } 
    hit[i] = 0; 
    walk(trie.subtrie[0], word, i+1, hit, (word[i]==0 ? budget : budget-1)); 
    hit[i] = 1; 
    walk(trie.subtrie[1], word, i+1, hit, (word[i]==1 ? budget : budget-1)); 
} 

main(){ 
    for (int budget = 0; ; budget++){ 
    walk(trie, word, 0, hit, budget); 
    /* quit if enough hits have been printed */ 
    } 
} 

L'idée est vous promenez l'ensemble Trie, garder une trace de la distance entre le nœud trie actuel et le mot d'origine. Vous élaguez la recherche en ayant un budget de combien de distance vous tolérerez. Cela fonctionne parce que la distance ne peut jamais diminuer au fur et à mesure que vous vous enfoncez dans le trie.

Ensuite, vous le faites à plusieurs reprises avec des budgets commençant à zéro et augmentant progressivement jusqu'à ce que vous imprimiez les hits que vous voulez. Puisque chaque promenade couvre autant de nœuds que la marche suivante, cela ne fait pas de mal de faire plusieurs marches. Si k est fixe, vous pouvez simplement commencer avec cela comme budget.