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.Struttura dati per trovare chiavi vicine con bitvalues simili
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.
Un'altra domanda: quante volte leggi e quante volte scrivi? Se scrivi raramente, potresti voler fare qualche calcolo preliminare, ma se stai leggendo e scrivendo costantemente questo non sarà il caso. –
@david, sì, questa è una considerazione importante. Ecco perché dico che la precomputazione, anche l'intenso preconcetto, è OK. Sto cercando di ottimizzare la velocità di ricerca. – SPWorley