hashing probabilistico - esiste una cosa del genere?

Question

Dire di voler implementare un click tracker in cui si desidera contare solo un clic su un collegamento da qualsiasi indirizzo IP una volta, ma il numero di collegamenti e client è molto grande e non si vuole tenere un tavolo di ogni singolo IP-click. Supponi che potresti aver bisogno di questo come parte di qualcosa che viene eseguito dal vivo contro ogni clic e non vuoi eseguire una ricerca su una grande tabella per ogni clic.

Esiste qualcosa come "hashing probabilistico" o "hashing lossy" per vedere se un IP è probabilmente in un set ma non ti interessa se c'è un certo tasso di errore come vuoi risparmiare risorse?

Answer 1

Si potrebbe probabilmente (ab?) Utilizzare uno bloom filter per qualcosa di simile.

Answer 2

Sicuro! Decidi quanti "bidoni" ti puoi permettere (ad un bit ciascuno), dì N; hash l'indirizzo IP a una stringa di bit B; prendi B modulo N. Puoi calcolare la probabilità di collisioni accidentali (con qualche approssimazione, ad esempio, supponi che tutti gli indirizzi IP con hash formino ugualmente probabili stringhe di bit B) e determini N di conseguenza se hai un vincolo sulla massima probabilità di collisione accidentale che è accettabile per il tuo applicazione.

Answer 3

Hash intero (ipv4) o stringa (ipv6) senza gestione della collisione, utilizzando il valore hash (dimensione tabella hash modulo) come indice di un array bitmap.

Answer 4

Tutto l'hashing è in perdita, in virtù dello pigeonhole principle. Inevitabilmente, stai cercando di raggruppare le cose N negli slot M (dove N >> M). Tutto quello che devi fare è semplicemente non gestire i casi di collisione e scegliere una tabella hash sufficientemente grande.

Answer 5

Assumendo indirizzi IPv4, vi è uno spazio di ricerca di 2 . Non è necessario più di 1 bit per indirizzo IP (0 == nessuna visita, 1 == visita). Senza considerare l'overhead di archiviazione, occorrerebbero 512 MB (2) da archiviare. Quindi un'implementazione semplicistica alloca un array da 512 MB (o una tabella con 2 righe, ognuna contenente un byte o 2 righe, ciascuna contenente un numero intero a 32 bit o 2 righe , ciascuna memorizza un numero intero a 64 bit, o ...)

È possibile ottimizzare questo per popolazione sparsa trasformandolo in un albero.

Definire una dimensione di "pagina" di 2 ^x bit. Assegnerai lo spazio di archiviazione per una pagina alla volta.

Dividere lo spazio di ricerca (2) in base alle dimensioni della pagina. Questo è il numero totale di pagine richieste per rappresentare ogni possibile indirizzo nel tuo spazio di ricerca.

Quindi, per determinare se c'è un hit nel tuo hash, dovrai prima determinare se la pagina è presente, e in tal caso, se è impostato il bit appropriato nella pagina. Per memorizzare un indirizzo nella cache, determinerai prima se la pagina è presente; se non lo creerai. Quindi imposterai il bit appropriato.

Questo stampo è abbastanza semplice per una tabella di database. Avresti bisogno solo di due colonne: un indice di pagina e un array binario. Quando si assegna una pagina, si memorizzerà semplicemente una riga nella tabella con l'indice di pagina corretto e una matrice binaria vuota.

Per esempio, per una dimensione di pagina 1024 bit (cedevole 2 pagine al massimo), si potrebbe strutturare la vostra tabella come questa:

CREATE TABLE VisitedIPs(
    PageIndex int   NOT NULL PRIMARY KEY, 
    PageData binary(128) NOT NULL 
) 

per verificare se un IP ha visitato, si usa codice simile (pseudocodice):

uint ip = address.To32Bit(); 

string sql = 
    "SELECT PageData " + 
    "FROM VisitedIPs " + 
    "WHERE PageIndex = " + (ip >> 10); 

byte[] page = (byte[])GetFromDB(sql); 

byte b = page[(ip & 0x3FF) >> 3]; 

bool hasVisited = (b & (1 << (ip & 7)) != 0; 

Impostazione che un IP ha visitato è simile:

uint ip = address.To32Bit(); 

string sql = 
    "SELECT PageData " + 
    "FROM VisitedIPs " + 
    "WHERE PageIndex = " + (ip >> 10); 

byte[] page = (byte[])GetFromDB(sql); 

page[(ip & 0x3FF) >> 3] |= (1 << (ip & 7)); 

sql = 
    "UPDATE VisitedIPs " + 
    "SET PageData = @pageData " + 
    "WHERE PageIndex = " + (ip >> 10); 

ExecSQL(sql, new SqlParam("@pageData", page)); 

Answer 6

Iniziare i bit di troncamento.

La probabilità di una collisione di hash diventa 50% quando si hanno 2^(n/2) cose da un possibile 2^n. Un indirizzo IP è 2^32 quindi c'è una probabilità del 50% di collisione quando 2^16 oggetti sono nel contenitore.

Diminuire quando ci si sente a proprio agio.