Name comparison

Patent metadata

Field	Value
Publication number	US-9691075-B1
Application number	US-201414214368-A
Country	US
Kind code	B1
Filing date	Mar 14, 2014
Priority date	Mar 14, 2014
Publication date	Jun 27, 2017
Grant date	Jun 27, 2017

Abstract

The present disclosure extends to comparing two or more names in a database of contact records. In embodiments, systems of the present disclosure execute a comparison of submitted names to determine if the records should be linked and/or merged. Embodiments of the present disclosure can compensate for irregularities in the database of contact records, including inconsistent name prefixes and suffixes, misspellings, typographical errors, misordered first/last names, and nicknames.

First claim

What is claimed is:

1. A computer-implemented method of comparing two contact records in a contact database, comprising:
receiving a first name and a second name;
at a computer processor of a name tokenizer module, tokenizing the first name, thereby generating a first set of tokens;
at the computer processor of the name tokenizer module, tokenizing the second name, thereby generating a second set of tokens;
at a data structure of a nickname module, searching for a first nickname corresponding to a selected token in the first set of tokens;
at a computer processor of the nickname module, adding the first nickname to a nickname set for the selected token in the first set of tokens;
at the data structure of the nickname module, searching for a second nickname corresponding to a selected token in the second set of tokens;
at the computer processor of the nickname module, adding the second nickname to a nickname set for the selected token in the second set of tokens;
at a computer processor of a token cross-multiplier module, cross-multiplying the first set of tokens with the nickname set for the selected token in the first set of tokens, thereby generating a first cross-multiplied token combination that includes each possible combination of the first set of tokens and the nickname set for the selected token in the first set of tokens;
at the computer processor of the token cross-multiplier module, cross-multiplying the second set of tokens with the nickname set for the selected token in the second set of tokens, thereby generating a second cross-multiplied token combination that includes each possible combination of the second set of tokens and the nickname set for the selected token in the second set of tokens;
at a computer processor of a token permutation module, generating a first permutation set from the first cross-multiplied token combination;
at the computer processor of the token permutation module, generating a second permutation set from the second cross-multiplied token combination;
at a computer processor of a string comparison module, comparing the first permutation set against the second permutation set; and
outputting a name comparison score.

2. The method of claim 1 , wherein generating the first permutation set further comprises:
cyclically permuting the first cross-multiplied token combination, thereby resulting in a permutated element;
concatenating the permutated element; and
adding the concatenated permutated element to the first permutation set.

3. The method of claim 1 , wherein generating the second permutation set further comprises concatenating elements of the second cross-multiplied token combination.

4. The method of claim 1 , wherein generating the second permutation set further comprises:
cyclically permuting the second cross-multiplied token combination, thereby resulting in a permutated element;
concatenating the permutated element; and
adding the concatenated permutated element to the second permutation set.

5. The method of claim 1 , further comprising:
at a computer processor of a token deduplication module, identifying any distinct tokens from the first set of tokens;
at the computer processor of the token deduplication module, inserting the distinct tokens from the first set of tokens into a first distinct token set;
at the computer processor of the token deduplication module, identifying any distinct tokens from the second set of tokens; and
at the computer processor of the token deduplication module, inserting the distinct tokens from the second set of tokens into a second distinct token set.

6. The method of claim 1 , further comprising merging the two contact records into a single contact record.

7. The method of claim 1 , further comprising linking a selected first one of the two contact records to a selected second one of the two contact records.

8. The method of claim 1 , wherein comparing the first permutation set against the second permutation set comprises calculating a minimum Levenshtein distance between members of the first permutation set and members of the second permutation set.

9. A system comprising a hardware device for providing a name comparison comprising:
a name tokenizer module adapted to tokenize a received name;
a token deduplication module adapted to identify a distinct token and add the distinct token to a distinct token set;
a nickname module adapted to identify and return a nickname for the distinct token;
a token cross-multiplier module adapted to:
receive the distinct token set and the nickname and
generate a cross product of the distinct token set and the nickname, the cross product comprising every possible combination of the tokens of the distinct token sets and nicknames for the tokens of the distinct token set;

a token permutation module adapted to concatenate the cross product, thereby generating a first permutated string; and
a string comparison module adapted to perform a string comparison between the first permutated string and a second permutated string.

10. The system of claim 9 , wherein the token permutation module is further adapted to carry out a cyclic permutation of the cross product.

11. The system of claim 9 , wherein the string comparison module is adapted to calculate an edit distance between the first permutated string and a second permutated string.

12. The system of claim 9 , further comprising a computer processor device coupled to a memory storing computer-readable instructions, the computer processor capable of:
tokenizing a first name and a second name, thereby generating a respective first and second set of tokens;
generating a nickname set, the nickname set corresponding to a selected token of the first or second set of tokens;
cross-multiplying the first set or the second set of tokens with the nickname set, thereby generating at least one cross-multiplied token combination;
generating a first string representation of a selected one of the at least one cross-multiplied token combination and generating a second string representation;
comparing the first string representation against the second string representation, thereby generating a name comparison score; and
outputting the name comparison score.

13. The system of claim 9 , where the nickname module comprises a vantage-point tree.

14. A computer-implemented method of comparing a two names, comprising:
at a computer processor of a name tokenizer module, tokenizing the two names, thereby generating a first and second set of tokens;
at a computer processor of a nickname module, generating a nickname set, the nickname set corresponding to a selected token of the first or second set of tokens;
at a computer processor of a token cross-multiplier module, cross-multiplying the first set or the second set of tokens with the nickname set, thereby generating at least one cross-multiplied token combination including every possible combination of the tokens of the first and nicknames of the nickname set;
generating a first string representation of a selected one of the at least one cross-multiplied token combination and generating a second string representation;
at a computer processor of a string comparison module, comparing the first string representation against the second string representation, thereby generating a name comparison score; and
outputting the name comparison score.

15. The method of claim 14 , wherein generating the first string representation of the selected one of the at least one cross-multiplied token combination comprises:
cyclically permuting the at least one cross-multiplied token combination, t

Assignees

• Wal Mart Stores Inc

Inventors

• Ray Andrew Benjamin
• Troutman Nathaniel Philip

Classifications

• G06Q30/0201 Primary

  Market modelling; Market analysis; Collecting market data · CPC title

• G06Q10/10

  Office automation; Time management · CPC title