Strategies for avoiding expensive batch searches

Question

We have a list of about 100, 000 customers. Every night, we run a batch search of these customer names against a list of known criminals/suspicious persons. This list contains around 1 million entries.

To ameliorate false-negatives, we're using fuzzy string matching which catches small mismatches between the customer names and the suspicious names lists.

The problem is that this search is incredibly slow (it might take days to finish).

What strategies can I consider in order to avoid checking customers again and again against some entries?

Note: The suspicious-persons list is updated every week with new entries.

Possible solutions

• I could keep a table that records which customers have been checked against which entries. However this is a terrible solution. I need to keep a record of 100,000 customers * 1 million entries in order to cover all the possibilities.

Answer 1

Consider a solution with the following parameters

a. The suspicious person list as it was the last time you ran the search
b. The customer list and the date when each customer was added to the system
c. The date when you last ran the search
d. The latest suspicious person list

The solution would:

1. Diff the latest suspicious persons list (d) against the list as it was last time you ran the search (a) to find the additions to the suspicious persons list
2. For customers added to the system after the date of the last search (c), match these customers against the latest suspicious persons list (d)
3. For all other customers, match them against the difference between the two lists (from 1.)
4. Update your stored suspicious persons list (a) from latest (d) and update (c) to the current time

Another thing you could do to speed up search (if you're not already doing it) is load your customers into a text search engine (e.g. ElasticSearch), and fuzzy search with the names on the suspicious persons list. If configured correctly the search engine will create an index that will make these searches fast.

Answer 2

It sounds like you're causing a full table scan for each name from the criminal list because you're using a fuzzy search.

I suggest you instead retrieve all customer information from the database and do the search in memory.

The following algorithm should work much faster:

1. Define a hash function F which creates hash values to enable a fuzzy search. I suggest you use something like a phonetic algorithm.
2. Load all required customer information from your database into a list C.
3. Read the criminal list L
4. Create a hashtable H (or dictionary/map) which maps hash values (usually int) to a list of strings.
5. For each name in L
   1. Create the hash value h using F
   2. Either insert a new list into H or add the name to an existing list based on h.
6. For each customer name in C
   1. Create the hash value h using F.
   2. If h is in contained in the hashtable, then you have the customer name and potential matches in the criminal list. Make further checks if necessary.
   3. If not then there are no names similar to the customer name

My quick'n'dirty implementation of this algorithm suggests for your current constraints (1 million entries in the criminal list and 100,000 customers) a runtime of <1 second.

Or more formally the runtime of this algorithm is O(n+m) where n is the number of customers and m the number of entries on the criminal list. (assuming O(1) for insert/lookup in the hashtable)