1

Here i am basically looking for performance improvement.

I need to match names in a SWIFT message (Let's say MT 103) against sanctions lists (sanctions lists by UN, by OFAC, some custom lists) and below is what i have developed

  1. Since there are various lists and total number of names are more than 50 thousand so i load all the names in a list instead of fetching them again and again from database
  2. Then i loop through the list and use Levenshtein distance, because there could be spelling mistakes, to find the difference between two names(one name from database and name in the SWIFT message) and store their differences
  3. Then i pick the top 10,50 or 100 names with least differences.

Since name fields in SWIFT messages are free-formatted four lines with 35 characters each and there is no rule to have a delimiter so you will find name, address and contact numbers mixed up together. For example the Remitter name would be like

ABCXYZ INTERNATIONAL PLASTIC INDUST
RIES PVT LTD 49-A, S.I.E A JOHANNES
BURG SOUTH AFRICA 

OR

Charles Philip Arthur George Mountb
atten-Windsor Buckingham Palace Wes
tminster London

Since there is no way to separate name with the address so i decided to create names from parts of these lines. For example

ABCXYZ
ABCXYZ INTERNATIONAL
ABCXYZ INTERNATIONAL PLASTIC
ABCXYZ INTERNATIONAL PLASTIC INDUSTRIES
ABCXYZ INTERNATIONAL PLASTIC INDUSTRIES PVT
ABCXYZ INTERNATIONAL PLASTIC INDUSTRIES PVT LTD
ABCXYZ INTERNATIONAL PLASTIC INDUSTRIES PVT LTD 49-A,
ABCXYZ INTERNATIONAL PLASTIC INDUSTRIES PVT LTD 49-A, S.I.E
...
INTERNATIONAL
INTERNATIONAL PLASTIC
INTERNATIONAL PLASTIC INDUSTRIES
...
PLASTIC 
PLASTIC INDUSTRIES 
PLASTIC INDUSTRIES PVT 
PLASTIC INDUSTRIES PVT LTD 
...

OR

Charles
Charles Philip
Charles Philip Arthur
...
George 
George Mountbatten-Windsor
George Mountbatten-Windsor Buckingham 
...
Buckingham 
Buckingham Palace
Buckingham Palace Westminster 
Buckingham Palace Westminster London
...
Westminster
Westminster London
London

The case would be similar with Beneficiary name. Sometimes the number of these combinations exceeds 200 and so comparing these 200 names with 50 thousand names of sanctions lists is quite expensive.

Here i need to improve the performance by identifying the name from these 4 lines somehow or extract candidate names from these combinations to shorten the list of names to be matched or extract candidate names from sanctions lists, etc

I am already using Parallel.ForEach which consumes 100% CPU which is not a feasible solution.

I need suggestions to improve the performance of this solution or a better solution.

Edit # 1

I used Fast approximate string matching with large edit distances in Big Data (2015) by Wolf Garbe and below is the result

Sanctioned names:           48, 290
Names screened:             360
Total time by Existing* Levenshtein:    468,575 ms (7.809 min)
Total time by Wolf Garbe Levenshtein:   177,862 ms (2.964 min)

Both these algos calculated the same distances for 57,961 varying name matchings. * Don't remember the source of this implementation.

  • 3
    Off-topic: Please, please tell me that the international financial system doesn't really rest on such absurdly error-prone and antediluvian message formats... – Kilian Foth Nov 5 '18 at 8:00
  • 1
    @KilianFoth ... and that payment rejections do not rely on some fuzzy matching of any word in an address that matches even remotely a name in a sanction list ;-) – Christophe Nov 5 '18 at 8:25
  • @KilianFoth I wish I could tell you that but as I am intimately familiar with SWIFT format and international wire transfers I can attest to the OP's question. Just keep in mind that financial institutions still use mainframes and the tech behind the SWIFT network is relatively unchanged since the 70's. – maple_shaft Nov 5 '18 at 13:03
  • While I work with sanctions screening software on payment systems, I am not terribly familiar with the algorithms used. What I might suggest though is looking into possibly building a balanced binary tree on the 50k or so current sanctions names so that you can quickly scan for matches by drilling down into the tree. Your more expensive operations would then be rebalancing the tree when inserts or deletes occur from the sanctions list. – maple_shaft Nov 5 '18 at 13:11
  • @maple_shaft binary tree might not be helpful due to spelling mistakes made by the end user e.g. if an entered name starts with A then i am not sure it is starting with A and it is not a spelling mistake. Won't it? – bjan Nov 5 '18 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.