Ho due elenchi (dimensioni m e n ) contenenti vettori di bit ad alta dimensione. Tutti i vettori hanno lo stesso numero di dimensioni e utilizzano Distanza di Hamming come misura se la distanza.
Per ogni elemento nel primo elenco voglio trovare gli elementi più vicini nel secondo elenco. Un elemento così vicino potrebbe differire di diverse migliaia di bit dall'elemento che sto cercando.
L'approccio ingenuo sarebbe calcolare la distanza di hamming per ogni coppia di vettori, ma ciò ha il tempo di esecuzione O (m * n) che lo rende impossibile. Quindi sto cercando un algoritmo che sia significativamente più veloce.
Diciamo che ho d = 10000, m = 1 miliardo e n = 100 miliardi e voglio che l'algoritmo termini in un paio di giorni di CPU.
Gli elementi nel primo elenco vengono creati prendendo un elemento casuale dalla seconda lista e sfogliando ogni bit con la stessa probabilità p < 0.5. Voglio supportare i valori di p che sono il più vicino possibile a 0,5. Sto bene con algoritmi probabilistici che trovano corrispondenze con alta probabilità.