Calcolatura della distanza di keting tra vettori binari

Question

Considera il seguente problema:

Ingresso: Ci viene dato un set $ s $ di $ n $ vettori binari. Un vettore binario è del modulo $ (b_0, b_1, ... b_n) $, dove $ b_i in {0, 1 } $. Pertanto, ci sono $ n $ vettori di dimensioni $ n $.

Produzione: Per ogni vettore in $ s $, vorremmo (in modo efficiente) calcolare un elenco di vettori binari da $ s $ la cui distanza di martello è in una costante predefinita $ c $.

Output (alternativa): Trova la coppia di vettori con una distanza minima di martellare.

---

Chiaramente, quanto sopra può essere fatto in $ o (n^3) $ calcolando la distanza di martello a coppie tra ciascun vettore in S ($ frac {n*(n+1)} {2} $ combinazioni a coppie e $ o (n) $ per calcolare la distanza di Hamming). Tuttavia, sto cercando qualcosa di più efficiente, poiché $ n $ può richiedere valori di grandi dimensioni (diciamo $ n = 10^6 $).

Per accelerare il calcolo, si potrebbe usare una qualche forma di hashing, in cui posizioniamo i vettori binari in secchi da $ n $, in cui ogni vettore nel bucket $ i^{th} $ contiene esattamente $ i $ quelli. Questo potrebbe funzionare, ma nel mio caso particolare, ci si potrebbe aspettare che tutti i vettori binari abbiano approssimativamente lo stesso numero di quelli, quindi non si guadagnerebbe molto da tale hashing. Si potrebbe anche cercare di eseguire una sorta di compressione sui vettori binari ed eseguire il calcolo della distanza di keting sui vettori compressi più piccoli come rilegato sulla distanza, ma sospetto che ci siano approcci migliori.

Un altro approccio di hashing sarebbe quello di suddividere lo spazio in ipercubi e posizionare ogni vettore in uno dei cubi. Credo che approcci simili siano usati nelle simulazioni di fisica, in cui lo spazio sarebbe diviso in un numero di cubi 2D o 3D e quindi calcola l'interazione di elementi all'interno di cubi e cubi vicini.

Ho visto variazioni di quanto sopra in molte applicazioni, ma non sono sicuro di quale sia il nome del problema o come calcolare in modo efficiente la soluzione. Vale la pena notare che nel mio caso particolare le soluzioni non devono essere "esatte", cioè ci possono essere alcuni errori nell'output fintanto che "la maggior parte" è corretta. Il problema principale sembra essere come evitare di calcolare la distanza tra vettori che sono chiaramente distanti.

(La struttura dei vettori binari in $ s $ può essere diversificata. In alcuni casi, ci sono pochi bit impostati in ciascun vettore, mentre in altri casi i vettori possono essere densi. Per la custodia scarsa, il calcolo della distanza di Hamming può ottenere notevolmente Spenso, ma il collo di bottiglia è il $ frac {n*(n+1)} {2} $ confronti che devono essere fatti.).