Che cos'è un buon algoritmo per verificare se un numero esiste in più set senza cercarli tutti?

Question

Scenario

Diciamo che dispone di più database in 3 zone. Zona A, B e C. Ogni zona in diversa posizione geografica. Allo stesso tempo, hai un'applicazione che instraderà nome utente e password in base alla posizione geografica dell'utente. Ad esempio, l'utente A verrà reindirizzato al database nella zona A. Utente B Zona B e così via.

Ora, diciamo che l'utente A si sposta in una zona B. La zona di domanda dell'applicazione B e non troverà nulla. La zona di interrogazione A e la zona C potrebbero impiegare un po 'di tempo a causa di zone molto lontane e dovranno interrogare tutti i database in tutte le zone.

La mia domanda

modo è possibile verificare se una stringa/numero esiste in più set?

o

Come si può verificare una riga esiste nel database prima anche l'invio di una query?

mio algoritmo

Questo non è perfetto, ma vi darà qualche idea di quello che sto cercando di fare

Se abbiamo la base di dati con i seguenti 3 utenti

• foo
• bar
• foobar

Prendiamo l'hash di tutti e 3 gli utenti e cerchiamo il prossimo numero primo se l'hash non è primo.

sum = hash(foo).nextPrime() * hash(bar).nextPrime() * hash(foobar).nextPrime() 

Quella somma è condivisa tra tutte le zone. Se voglio controllare lo foo, posso semplicemente prendere l'hash di foo, e cercare il prossimo primo, quindi prendere lo gcd(foo,sum). Se non è uguale a uno. Significa che foo esiste in qualche database. Se è uguale a uno, significa che foo non esiste affatto. Se voglio aggiungere un nuovo nome utente. Posso semplicemente fare sum = sum * hash(newUserName).nextPrime().

Sum crescerà fino a un punto che sarà più veloce per interrogare tutti i database.

Conosci un algoritmo simile per risolvere questo problema?

Answer 1

Una struttura dati adatta per questa applicazione è Bloom filter.

Un filtro Bloom è una struttura di dati probabilistica che consente di verificare se un elemento è già presente in un set. Se il test restituisce false, l'elemento non è sicuramente nel set (0% falsi negativi), se è vero allora potrebbe essere nel set, ma non è garantito che sia (i falsi positivi sono possibili).

Il filtro è implementato come un array di bit con m bit e un insieme di k funzioni di hash. Per aggiungere un elemento all'array (ad esempio un nome utente), cancellare l'elemento utilizzando ciascuna delle funzioni di hash e quindi prendere il modulo m di ciascun valore di hash per calcolare gli indici da impostare nell'array di bit. Per verificare se un elemento è nell'insieme, calcolare tutti gli hash e gli indici e controllare che tutti i bit corrispondenti dell'array siano impostati su 1. Se uno di essi è zero, l'elemento non è sicuramente nell'insieme, se tutto sono 1 quindi l'oggetto è molto probabilmente nel set, ma c'è una piccola possibilità che non lo sia, la percentuale di falsi positivi può essere ridotta usando un m più grande.

Per implementare le funzioni di hash k, è possibile utilizzare solo lo stesso algoritmo di hash (ad esempio CRC32, MD5 ecc.) Ma aggiungere diversi sali alla stringa nome utente prima di passare alla funzione hash, creando in modo efficace "nuovo" funzioni di hash per ogni sale. Per un dato m e n (numero di elementi aggiunti), il numero ottimale di funzioni hash è k = (m/n) ln 2

Per l'applicazione, l'array di bit del filtro Bloom sarà condiviso in tutte le zone ABC ecc. Quando un utente tenta di accedere, è possibile prima controllare il database della zona locale e, se presente, registrarli come di consueto. Se non è presente nel database locale, controlla il filtro Bloom e se il risultato è negativo, allora sai per certo che non esistono in un'altra zona. Se è positivo, è comunque necessario controllare i database nelle altre zone (a causa della possibilità di un falso positivo), ma presumibilmente questo non è un grosso problema, perché in ogni caso dovresti contattare le altre zone per trasferire l'utente dati nel caso in cui fosse un vero positivo.

Un lato negativo dell'utilizzo di un filtro Bloom è che è difficile (anche se not impossible) rimuovere elementi dal set dopo che sono stati aggiunti.