Supplier deduplication engine

• US 8,234,107 B2
• Filed: 02/12/2008
• Issued: 07/31/2012
• Est. Priority Date: 05/03/2007
• Status: Active Grant

• Current Assignee: Ketera Technologies Inc. (Jack Taylor Family Voting Trust U A D 4 14 99)
• Original Assignee: Ketera Technologies Inc. (Jack Taylor Family Voting Trust U A D 4 14 99)
• Inventors: Goyal, Ram Dayal
• Primary Examiner(s): COLUCCI, MICHAEL C
• Application Number:
  US12/029,519
• Publication Number:
  US 20080275874A1
• Time in Patent Office: 1,631 Days
• Field of Search: 715/822, 715/210, 715/261, 704/246, 704/240, 704/4, 704/9, 714/1, 707/7, 235/494, 382/181
• US Class Current: 704/4
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

Abstract

Disclosed herein is a method of grouping similar supplier names together in a database. The syntactical errors in the supplier names are corrected. The supplier names are grouped after correcting the syntactical errors. The abbreviations in the supplier names are captured. The ordering, pronunciation and stemming errors in the supplier names are corrected. A matching algorithm that matches and compares two supplier names is applied that comprises the steps of grouping supplier names based on first set of characters in the supplier names and calculating a matching score between the two supplier using Levenshtein distance between the two supplier names, along with the supplier names'"'"' sound codes obtained from a modified metaphone algorithm, length of each word, position of matching and mismatching characters, and stem of words in the supplier names. The matching scores are compared with set thresholds in order to further group the supplier names into clusters.

Claims

1. A method for deduplication and grouping similar supplier names from a plurality of supplier names, comprising:

correcting syntactical errors in said supplier names;

grouping the supplier names after said step of correcting syntactical errors;

capturing abbreviations of the supplier names;

correcting ordering, pronunciation and stemming errors in the supplier names;

calculating a name matching score between two of said supplier names using a matching algorithm, comprising the steps of;

grouping supplier names based on the first set of characters in the supplier names;

calculating a word matching score between corresponding words in two of said supplier names, comprising;

determining stems of said corresponding words;

determining sound codes of said determined stems using a modified metaphone algorithm;

determining a Levenshtein distance between said sound codes;

calculating a prefix score using said stems and calculating a sound score using said sound codes;

calculating a Levenshtein distance score using said determined Levenshtein distance and length of larger of said corresponding words;

selecting one of said prefix score, said sound score and said Levenshtein distance score as said word matching score based on comparisons with a set threshold;

calculating said name matching score between two of said supplier names based on said word matching score; and

comparing said name matching score with a threshold value to determine a match, and grouping said supplier names based on said match.

2. The method of claim 1, further comprising the step of applying manual intervention to make a final decision.

3. The method of claim 1, wherein said grouping is agglomerative and the grouping result is normalized in the form of a table.

4. The method of claim 3, wherein said agglomerative grouping is performed in a plurality of levels.

5. The method of claim 4, wherein the first level out of said plurality of levels comprises correcting said syntactical errors and capturing said abbreviations.

6. The method of claim 4, wherein the second level out of said plurality of levels comprises handling said order of words, said pronunciation errors and said stemming errors.

7. The method of claim 4, wherein the third level out of said plurality of levels comprises grouping of clusters created in said second level using approximate string matching criteria.

8. The method of claim 7, wherein said string matching criteria comprises said Levenshtein distance scores, position of matching and non-matching characters, number of words, length of words, etc.

9. The method of claim 4, wherein the fourth level out of said plurality of levels comprises manual verification in order to verify the accuracy in grouping and identify probable matches in supplier names.

10. The method of claim 4, further comprising the step of setting threshold values for all said levels of grouping of supplier names.

11. The method of claim 7, further comprises the steps of comparing said matching scores with said set thresholds, and if the matching score is greater than the set threshold, said supplier names are merged in third level.

12. The method of claim 1, wherein the number of words in said supplier names and the number of words matching between said two supplier names is considered for determining name matching scores between the two supplier names in said matching algorithm.

13. The method of claim 1, wherein the position of mismatching characters is considered for determining said word matching scores between said two supplier names in said matching algorithm.

14. The method of claim 1, wherein the length of each word present in said supplier names is considered in said matching algorithm.

15. The method of claim 1, wherein small sub groups of supplier names are created based on a similar first set of characters, wherein said step of creating small sub groups eliminates unnecessary matches.

16. The method of claim 1, wherein said supplier names are grouped by assigning same record identifiers to matched supplier names at different levels of grouping, whereby each group comprises a unique identifier.

17. The method of claim 1, wherein common words and word forms in said supplier names are ignored before grouping the supplier names.

18. A computer program product comprising computer executable instructions embodied in a non-transitory computer-readable medium, said computer program product including:

a first computer parsable program code for correcting syntactical errors in supplier names;

a second computer parsable program code for grouping the supplier names after said step of correcting syntactical errors;

a third computer parsable program code for capturing abbreviations of the supplier names;

a fourth computer parsable program code for correcting ordering, pronunciation and stemming errors in the supplier names;

a fifth computer parsable program code of a matching algorithm to calculate a name matching score between two of said supplier names, comprising;

a sixth computer parsable program code for grouping supplier names based on the first set of characters in the supplier names to avoid unnecessary squared n matching;

a seventh computer parsable program code for calculating a word matching score between corresponding words in two of said supplier names, comprising;

an eighth computer parsable program code for determining stems of said corresponding words;

a ninth computer parsable program code for determining sound codes of said determined stems using;

a tenth computer parsable program code for determining a Levenshtein distance between said sound codes;

a eleventh computer parsable program code for calculating a prefix score using said stems and calculating a sound score using said sound codes;

a twelfth computer parsable program code for calculating a Levenshtein distance score using said determined Levenshtein distance and length of larger of said corresponding words;

a thirteenth computer parsable program code for selecting one of said prefix score, said sound score and said Levenshtein distance score as said word matching score based on comparisons with a set threshold;

a fourteenth computer parsable program code for calculating said name matching score between two of said supplier names based on said word matching score; and

a fifteenth computer parsable program code for comparing said name matching score with a threshold value to determine a match, and grouping said supplier names based on said match.