Filtri di fioritura o simili, ma senza falsi positivi

Question

Filtri di fioritura o simili, ma senza falsi positivi

#1 da (4 voti)

6

Per migliorare alcune ricerche, sto prendendo in considerazione l'uso di Bloom Filters. Ma nel mio caso d'uso, il risultato più probabile è che l'elemento esista nel set di destinazione.

I filtri Bloom possono avere falsi positivi, ma non falsi negativi. Questo mi farebbe controllare la memoria reale (grande e lento) la maggior parte del tempo a causa delle incertezze.

Esiste un'altra struttura algoritmo / dati con le stesse proprietà per lo spazio e la velocità di calcolo (e il parallelismo della query) che non può garantire falsi positivi e una bassa probabilità di falsi negativi?

(La dimensione massima del set sarà di circa 300k elementi, gli elementi saranno stringhe di, al massimo, 512 caratteri, e avrò centinaia di set come quello.)

data-structures algorithms filtering

posta Fernando 10.01.2014 - 15:35

fonte

1 risposta

Leggi altre domande sui tag data-structures algorithms filtering

Distribuzione dell'app basata su Qt su Mac OS X. Una classe dovrebbe implementare esplicitamente l'interfaccia se anche la sua superclasse la implementa?

score 4 · Accepted Answer

La cosa bella dei filtri di fioritura è che il loro requisito di spazio può essere ridimensionato in modo arbitrario, con il costo di più falsi positivi quando la dimensione viene ridotta.

Se non si desidera alcun falso positivo, non è possibile utilizzare scorciatoie probabilistiche e non sarà in grado di ridurre significativamente i requisiti di spazio (il che non è tanto un problema dato che l'archiviazione sequenziale di ciascuna delle stringhe verrebbe utilizzata solo poche centinaia di MB per set).

Esistono due rappresentazioni importanti di set di stringhe:

tabelle hash e
tentativi .

Queste strutture dati consentono l'accesso parallelo e ogni accesso è O (1) rispetto al numero di elementi nel set.

Tries ha il vantaggio di condividere i prefissi comuni delle stringhe, riducendo potenzialmente i requisiti di spazio al di sotto di quelli della memorizzazione sequenziale. Un trie di sola lettura può anche essere ulteriormente compresso.