Strutture dati probabilistiche efficienti in termini di spazio per il recupero dei numeri

Question

Consideriamo che abbiamo un algoritmo che riceve un flusso di chiavi ipoteticamente lungo. Quindi genera un valore compreso tra 0 e 1 per ogni chiave, mentre la elaboriamo, per il recupero posteriore. Il set di input è abbastanza grande da non poterci permettere di memorizzare un valore per ogni chiave. La regola di generazione del valore è indipendente tra le chiavi.

Ora, supponiamo che possiamo tollerare errore nella ricerca posteriori, ma vogliamo ancora ridurre al minimo la differenza direcuperate e valori originali (cioè asintoticamente nel corso di molti recuperi casuali).

Ad esempio, se il valore originale per un determinato tasto era 0,008, il recupero di 0,06 è molto meglio del recupero di 0,6.

Quali strutture dati o algoritmi possiamo utilizzare per risolvere questo problema?

I filtri Bloom sono la struttura dati più vicina a cui possa pensare. Si potrebbe quantizzare il range di output, usare un filtro di fioritura per ciascun bucket e in qualche modo combinare il loro output al momento del recupero per stimare il valore più probabile. Prima di procedere con questo percorso e reinventare la ruota, esistono strutture dati, algoritmi, approcci teorici o pratici noti per affrontare questo problema?

Sono idealmente alla ricerca di una soluzione che può parametrizzare il compromesso tra spazio e tassi di errore.

Answer 1

Forse una variante del filtro Bloom chiamato Compact Approximator: come un filtro di fioritura ma generalizzato in modo che le voci siano valori di un reticolo. Quel reticolo è qui fluttua tra 0 e 1 (ha più struttura del semplice reticolato ma soddisfa i requisiti) o comunque stai memorizzando quei numeri.

Un aggiornamento sostituisce le voci pertinenti per il massimo tra esso e il valore da ricordare, una query calcola il minimo di tutte le voci pertinenti (esempi di seguito). I risultati possono solo sovrastimare il vero valore. Invertendo l'ordine (scambiando min e max e inizializzando a 1 invece di 0) è possibile ottenere una sottostima, dando insieme un intervallo che contiene il valore reale.

---

Così, per esempio, utilizzando i primi approssimati (sovrastima), mettendo in un certo numero si presenta così:

index1 = hash1(key) 
data[index1] = max(data[index1], value); 
index2 = hash2(key) 
data[index2] = max(data[index2], value); 
... etc 

E ricevendo il sovrastima assomiglia:

result = 1 
index1 = hash1(key) 
result = min(data[index1], result); 
index2 = hash2(key) 
result = min(data[index2], result); 
... etc