Quale struttura dati per memorizzare stringhe binarie e interrogare con hamming distane

Question

Sto cercando una struttura dati per gestire miliardi di stringhe binarie che contiene 512 valori binari.

Il mio obiettivo è inviare i querys alla struttura e ottenere un set di risultati che contenga tutti i dati a una distanza inferiore.

La mia prima idea era usare un albero kd. Ma quegli alberi sono molto lenti per una dimensione elevata. La mia seconda idea è usare un approccio lsh (minHash/superbit) lsh. Ma per quello devo anche avere una struttura per effettuare ricerche efficienti

Qualche idea su come gestire questi big data?

** Aggiornamento ** Alcune note di dettaglio:

• per la distanza di Hamming esiste solo un limite massimo che è forse 128. Ma nel tempo che non conosce il limite superiore
• un inserimento o una delezione sarebbe bello, ma ho anche può ricostruire il grafico (la base dati solo aggiornato onces una settimana)
• il set di risultati deve contenere tutti i nodi rilevanti (io non sto cercando KNN)

Answer 1

Senza conoscere i parametri di ricerca previsti, è difficile essere troppo ottimizzati. Detto questo, penso che un buon approccio sarebbe quello di costruire un albero B o T e quindi ottimizzare quella struttura per la natura binaria dei dati.

In particolare, si dispone di 64 byte di dati come una stringa di bit di 512 elementi. La tua stima è che avrai "miliardi" di record. Questo è nell'ordine di 2 valori , quindi 1/16 ^th dello spazio sarà pieno? (Questo è in accordo con le vostre aspettative?)

In ogni caso, provare a suddividere i dati in byte, lasciare che ogni byte sia un livello chiave. Probabilmente puoi comprimere i record di livello, se la probabilità di set bit è uniforme. (In caso contrario, se i bit del set sono più probabili nella parte anteriore della chiave, potresti semplicemente assegnare 256 puntatori di livello successivo e alcuni essere nulli. Non vale sempre la pena.)

Tutti i tuoi i livelli saranno uguali: rappresenteranno altri 8 bit della stringa. Quindi calcola una tabella che mappa, per un byte, tutti i valori di byte che si trovano nella distanza da quel byte, 0 < = S < = 8. Inoltre, calcola una tabella che associa due byte alla distanza E tra loro, hamming(a,b).

Per attraversare l'albero, lasciare che la distanza di ricerca sia SD. Impostare D = SD. Leggi il blocco di livello superiore. Trova tutti i valori di 8 bit nel blocco meno della distanza min(8, D) dalla query. Per ogni valore, calcolare la distanza esatta hamming(query, value) e recurse al blocco inferiore con D = D - hamming(query, value) per tale sottoalbero.

Answer 2

Il più grande problema di progettazione che vedo qui è il requisito di chiusura: abbiamo bisogno di tornare tutti gli articoli breve distanza N di un dato vettore, per arbitraria N. Lo spazio dati è scarso: "miliardi" è nell'ordine di 2^33, ma abbiamo 512 bit di informazione, quindi c'è solo una voce per 2^(512-33) possibilità. Per chiavi distribuite casualmente, la distanza prevista tra due nodi qualsiasi è 256; la distanza attesa dal vicino più vicino è circa 180.

Questo mi porta ad aspettarmi che la tua ricerca dipenda da cluster di dati non casuali, e che la tua ricerca sarà facilitata dal riconoscimento di tale clustering. Questo sarà un passo di pre-elaborazione piuttosto doloroso sui dati iniziali, ma dovrebbe valere la pena.

Il mio approccio generale a questo è identificare i cluster in un modo generalmente veloce. Inizia con una funzione di hashing che restituisce una metrica di distanza molto generale. Ad esempio, per qualsiasi vettore, calcola le distanze da ognuno di un insieme di vettori di riferimento ortogonali. Per 16 bit, si può prendere il seguente set (elencato in hex): 0000, 00FF, 0F0F, 3333, 5555, una successiva "grana" di bit alternati. "Restituire questo hash come una semplice tupla le distanze a 4 bit, un totale di 20 bit (ci sono risparmi effettivi per i vettori lunghi, dato che una delle dimensioni è 2^(2^N))

Ora, questa tupla di hash ti consente di ottenere una stima approssimativa della distanza di hamming, in modo tale da possono raggruppare i vettori più facilmente: vettori che sono simili must hanno valori hash simili

da ciascun cluster, per un elemento centrale, e quindi caratterizzare ogni elemento del cluster dalla sua distanza da detto centro Per maggiore velocità.. , dai a ciascun nodo un elenco dei suoi vicini più vicini con le distanze, tutti all'interno di t lui cluster. Questo ti dà un grafico per ogni cluster.

Analogamente, connettere tutti i centri del cluster, fornendo bordi diretti ai centri del cluster più vicini. Se i tuoi dati sono ragionevolmente suscettibili alla ricerca, saremo in grado di garantire che, per ogni due nodi A, B con centri cluster Ac e Bc, avremo d (A, Ac) + d (B, Bc) < d (A, B). Ogni cluster è un quartiere topologico.

---

Il processo di query è ora un po 'più veloce. Per un vettore di destinazione V, trova il valore di hash. Trova centri di aggregazione abbastanza vicini da poter abbinare qualcosa nel loro vicinato ([distanza effettiva] - [intervallo di query] - [raggio di cluster]). Ciò ti consentirà di eliminare immediatamente interi cluster e potrebbe darti un intero gruppo di "colpi". Per ogni cluster marginale (alcuni, ma non tutti i nodi sono qualificati), dovrai trovare un nodo che funzioni in base a qualcosa di simile alla forza bruta (iniziare nel mezzo dell'intervallo di distanze percorribili dal centro del cluster), e poi fare una ricerca in ampiezza dei vicini di ogni nodo.

Mi aspetto che questo ti dia qualcosa di paragonabile a una prestazione ottimale. Inoltre, si adatta in modo decente alle aggiunte e alle eliminazioni, a condizione che non siano abbastanza frequenti da modificare l'appartenenza al cluster per altri nodi.

---

L'insieme di vettori è semplice. Scrivi i modelli di bit per il caso a 16 bit:

0000 0000 0000 0000 16 0s 
0000 0000 1111 1111 8 0s, 8 1s 
0000 1111 0000 1111 4 0s, 4 1s, repeat 
0011 0011 0011 0011 2 0s, 2 1s, repeat 
0101 0101 0101 0101 1 0s, 1 1s, repeat