Struttura dati per trovare chiavi vicine con bitvalues ​​simili

Question

Ho alcuni dati, fino a un valore compreso tra un milione e un miliardo di record, ognuno dei quali è rappresentato da un bitfield, circa 64 bit per chiave. I bit sono indipendenti, puoi immaginarli fondamentalmente come bit casuali.

Se ho una chiave di test e voglio trovare tutti i valori nei miei dati con la stessa chiave, una tabella hash li sputer molto facilmente, in O (1).

Quale algoritmo/struttura dati troverà in modo efficiente tutti i record più simili alla chiave di query? Qui in modo simile significa che molti bit sono identici, ma un numero minimo può essere sbagliato. Questo è tradizionalmente misurato da Hamming distance., che conta solo il numero di bit non corrispondenti.

Ci sono due modi in cui questa query può essere fatta, uno potrebbe essere specificando un tasso di corrispondenza errata come "dammi un elenco di tutte le chiavi esistenti che hanno meno di 6 bit che differiscono dalla mia query" o semplicemente le migliori corrispondenze, come "dammi una lista delle 10.000 chiavi che hanno il minor numero di bit diversi dalla mia query."

Si potrebbe essere tentati di correre a k-nearest-neighbor algorithms, ma qui stiamo parlando di bit indipendenti, quindi non sembra probabile che strutture come quadtrees sono utili.

Il problema può essere risolto con la semplice forza bruta testando una tabella hash per un numero basso di bit diversi. Se vogliamo trovare tutte le chiavi che differiscono di un bit dalla nostra query, ad esempio, possiamo enumerare tutte le 64 possibili chiavi e testarle tutte. Ma questo esplode rapidamente, se volessimo consentire due bit di differenza, allora dovremmo sondare 64 * 63 = 4032 volte. Diventa esponenzialmente peggiore per un numero maggiore di bit.

Quindi c'è un'altra struttura dati o una strategia che rende questo tipo di query più efficiente? Il database/struttura può essere pre-elaborato quanto vuoi, è la velocità della query che dovrebbe essere ottimizzata.

Answer 1

Quello che vuoi è un BK-Tree . È un albero che è l'ideale per indicizzare gli spazi metrici (il tuo problema è uno) e supporta sia le domande vicine che quelle a distanza. Ho scritto an article a riguardo qualche tempo fa.

Gli alberi BK sono generalmente descritti con riferimento al testo e utilizzano la distanza di levenshtein per costruire l'albero, ma è semplice scriverne uno in termini di stringhe binarie e distanza di hamming.

Answer 2

Bene, è possibile inserire tutte le chiavi vicine insieme alla chiave originale. Ciò significherebbe che si memorizzano (64 scelgono k) volte più dati, per k bit diversi, e sarà necessario decidere in anticipo k. Sebbene tu possa sempre estendere k per forza bruta interrogando i vicini, e questo interrogherà automaticamente i vicini dei tuoi vicini che hai inserito. Questo ti dà anche un compromesso spazio-tempo: ad esempio, se accetti un 64 xup di dati e 64 volte più lentamente puoi ottenere due bit di distanza.

Answer 3

Vorrei andare con un inverted index, come un motore di ricerca. Hai fondamentalmente un vocabolario fisso di 64 parole. Quindi la somiglianza viene misurata misurando la distanza, anziché la somiglianza del coseno come un motore di ricerca vorrebbe usare. La costruzione dell'indice sarà lenta, ma dovresti essere in grado di interrogarla con normali velocità di ricerca.

Il libro Introduction to Information Retrieval riguarda la costruzione efficiente, la conservazione, la compressione e l'interrogazione di indici invertiti.

Answer 4

"Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions", dal 2008, sembra essere il miglior risultato di allora. Non cercherò di riassumere poiché l'ho letto più di un anno fa ed è peloso. È da una pagina su locality-sensitive hashing, insieme a un'implementazione di una versione precedente dello schema. Per ulteriori suggerimenti generali, consultare nearest neighbor search.

Questo tipo di domanda è stato chiesto prima: Fastest way to find most similar string to an input?

Answer 5

Questo suona come una buona misura per un S-albero, che è come un file gerarchica rovesciata.Buone risorse su questo argomento includono i seguenti documenti:

Hierarchical Bitmap Index: An Efficient and Scalable Indexing Technique for Set-Valued Attributes.

Improved Methods for Signature-Tree Construction (2000)

citazione dal primo:

Il gerarchica indice bitmap e ffi cienza supporta dif- classi ferenti di query, comprese le domande su sottoinsiemi, superset e similitudine. I nostri esperimenti mostrano che l'indice bitmap gerarchico supera le altre tecniche di indicizzazione dell'insieme in modo signi fi cativo.

Questi documenti includono riferimenti ad altre ricerche che potrebbero essere utili, come ad esempio M-Trees.

Answer 6

Creare un albero binario (in particolare uno trie) che rappresenta ciascuna chiave nel set di avvio nel seguente modo: Il nodo radice è la parola vuota, spostandosi lungo l'albero a sinistra si aggiunge uno 0 e spostandosi a destra si aggiunge un 1. L'albero avrà tante foglie quante il tuo set iniziale ha elementi, quindi la dimensione dovrebbe rimanere gestibile.

Ora è possibile eseguire un attraversamento ricorsivo di questo albero, consentendo al massimo n "deviazioni" dalla chiave di query in ogni riga ricorsiva di esecuzione, fino a quando non si sono trovati tutti i nodi nel set di avvio che si trovano all'interno di quel numero di deviazioni.

Answer 7

Se i dati non erano così sparsi, un grafico con i tasti come i vertici e i bordi che collegano i nodi "adiacenti" (Hamming distance = 1) sarebbe probabilmente molto efficiente in termini di tempo. Lo spazio sarebbe molto grande, quindi nel tuo caso, non penso che sarebbe un compromesso utile.

Answer 8

Non ci ho pensato completamente, ma ho un'idea di dove iniziare.

Si potrebbe dividere lo spazio di ricerca in un certo numero di secchi in cui ciascun segmento ha un secchio chiave e le chiavi nel secchio sono le chiavi che sono più simili a questa chiave secchio di qualsiasi altro tasto secchio. Per creare le chiavi del bucket, è possibile generare casualmente chiavi a 64 bit e scartare quelle che sono troppo vicine a qualsiasi chiave bucket precedentemente creata oppure è possibile elaborare un algoritmo che generi chiavi abbastanza dissimili. Per trovare la chiave più vicina a una chiave di test, trovare prima la chiave del bucket più vicina e quindi testare ogni chiave nel bucket. (In realtà, è possibile, ma non è probabile, che la chiave più vicina si trovi in ​​un altro bucket: devi trovare la chiave più vicina o una chiave molto vicina deve essere abbastanza buona?)

Answer 9

Se si sta bene con un algoritmo randomizzato (monte carlo in questo caso), è possibile utilizzare lo minhash.

Answer 10

Il database/struttura può essere pre-elaborato come quanto volete

Beh ... SE che è vero. Quindi tutto ciò di cui hai bisogno è una matrice di similarità delle tue distanze di hamming. Rende la matrice sparsa potando le grandi distanze. Non diventa più veloce e non è un granché di memoria.

Answer 11

• strutture dati per grandi insiemi descritti qui: Detecting Near-Duplicates for Web Crawling o
• in memoria trie: Judy-arrays at sourceforge.net

Answer 12

Supponendo di avere a visitare ogni riga per testare il suo valore (o se si indice sul campo di bit quindi ogni voce indice), quindi è possibile scrivere il test effettivo in modo abbastanza efficiente utilizzando

A xor B

Per trovare i bit di differenza, quindi contare il risultato a bit, utilizzando una tecnica come this.

Questo effettivamente ti dà la distanza di hamming.

Dal momento che questo può compilare fino a decine di istruzioni per test, questo può essere eseguito piuttosto velocemente.

Answer 13

Se siete male con farlo probabilisticamente, penso che ci sia un buon modo per risolvere domanda 2. suppongo avete 2^30 dati e cutoff e si desidera trovare tutti i punti all'interno cutoff distanza dal test.

 
One_Try() 
    1. Generate randomly a 20-bit subset S of 64 bits 
    2. Ask for a list of elements that agree with test on S (about 2^10 elements) 
    3. Sort that list by Hamming distance from test 
    4. Discard the part of list after cutoff 

ripetere One_Try per quanto è necessario, mentre la fusione delle liste. Più tentativi hai, più punti trovi. Ad esempio, se x si trova entro 5 bit, lo troverai in una prova con circa (2/3)^5 = 13% di probabilità. Pertanto se si ripetono 100 tentativi, si trovano tutti, ma approssimativamente 10^{- 6} di tale x. Tempo totale: 100*(1000*log 1000).

Il vantaggio principale di questo è che siete in grado di risposte di uscita alla domanda 2, come si procede, dal momento che dopo i primi tentativi troverete sicuramente tutto raggiungibile a non più di 3 bit, ecc

Se disponi di molti computer, dai a ciascuno di essi diversi tentativi, poiché sono perfettamente parallelizzabili: ciascun computer salva in anticipo alcune tabelle di hash.