Strategie per evitare costose ricerche di lotti

Question

Strategie per evitare costose ricerche di lotti

#1 da (3 voti)
#2 da (1 voti)

0

Abbiamo un elenco di circa 100.000 clienti. Ogni notte, eseguiamo una ricerca batch di questi nomi di clienti contro un elenco di criminali noti / persone sospette. Questo elenco contiene circa 1 milione di voci.

Per migliorare i falsi negativi, stiamo utilizzando la corrispondenza di stringa fuzzy che cattura piccole discrepanze tra i nomi dei clienti e gli elenchi di nomi sospetti.

Il problema è che questa ricerca è incredibilmente lenta (potrebbero volerci giorni per finire).

Quali strategie posso prendere in considerazione per evitare di controllare i clienti ancora e ancora contro alcune voci?

Nota: l'elenco delle persone sospette viene aggiornato ogni settimana con nuove voci.

Possibili soluzioni

Potrei tenere una tabella che registra quali clienti sono stati controllati rispetto a quali voci. Tuttavia questa è una soluzione terribile. Devo tenere un registro di 100.000 clienti * 1 milione di voci per coprire tutte le possibilità.

optimization caching

posta Nik Kyriakides 19.07.2017 - 07:17

fonte

2 risposte

Leggi altre domande sui tag optimization caching

OpenID Connect - Endpoint UserInfo Ridondante? In che modo le possibilità di fallimento del progetto si riferiscono alle dimensioni del progetto? [chiuso]

score 3 · Answer 1

Considera una soluzione con i seguenti parametri

a. La lista delle persone sospette com'era l'ultima volta che hai eseguito la ricerca
b. L'elenco dei clienti e la data in cui ogni cliente è stato aggiunto al sistema
c. La data in cui è stata eseguita l'ultima ricerca
d. L'elenco delle persone sospette più recenti

La soluzione sarebbe:

Diff l'ultima lista di persone sospette (d) contro l'elenco poiché era l'ultima volta che hai eseguito la ricerca (a) per trovare le aggiunte all'elenco delle persone sospette
Per i clienti aggiunti al sistema dopo la data dell'ultima ricerca (c), abbinare questi clienti alla lista delle persone sospette più recenti (d)
Per tutti gli altri clienti, confrontali con la differenza tra i due elenchi (da 1.)
Aggiorna l'elenco delle persone sospette memorizzate (a) dall'ultima (d) e dall'aggiornamento (c) all'ora corrente

Un'altra cosa che potresti fare per velocizzare la ricerca (se non lo stai già facendo) è caricare i tuoi clienti in un motore di ricerca testuale (ad esempio ElasticSearch) e cercare fuzzy con i nomi nell'elenco delle persone sospette. Se configurato correttamente, il motore di ricerca creerà un indice che renderà queste ricerche veloci.

score 1 · Answer 2

Sembra che tu stia causando una scansione completa della tabella per ciascun nome dall'elenco criminale perché stai utilizzando una ricerca fuzzy.

Ti suggerisco invece di recuperare tutte le informazioni sui clienti dal database e di effettuare la ricerca in memoria.

Il seguente algoritmo dovrebbe funzionare molto più velocemente:

Definisci una funzione hash F che crea valori hash per abilitare una ricerca fuzzy. Ti suggerisco di utilizzare qualcosa come un algoritmo fonetico .
Carica tutte le informazioni sui clienti richieste dal tuo database in un elenco C .
Leggi la lista criminale L
Crea un hashtable H (o dizionario / mappa) che mappa i valori hash (di solito int) in un elenco di stringhe.
Per ogni nome in L
1. Crea il valore hash h utilizzando F
2. Inserisci una nuova lista in H o aggiungi il nome a un elenco esistente basato su h .
Per ogni nome cliente in C
1. Crea il valore hash h utilizzando F .
2. Se h è contenuto nella tabella hash, hai il nome del cliente e le potenziali corrispondenze nella lista criminale. Effettua ulteriori controlli se necessario.
3. In caso contrario, non ci sono nomi simili al nome del cliente

L'implementazione rapida di questo algoritmo suggerisce per i tuoi attuali vincoli (1 milione di voci nella lista criminale e 100.000 clienti) un tempo di esecuzione di < 1 secondo.

O più formalmente il runtime di questo algoritmo è O (n + m) dove n è il numero di clienti e m il numero di voci sulla lista criminale. (assumendo O (1) per insert / lookup nella tabella hash)