METHODS AND SYSTEMS FOR IMPLEMENTING APPROXIMATE STRING MATCHING WITHIN A DATABASE

• US 20090171955A1
• Filed: 12/31/2007
• Published: 07/02/2009
• Est. Priority Date: 12/31/2007
• Status: Active Grant

• Current Assignee: Mastercard International Incorporated (MasterCard Incorporated)
• Original Assignee: Mastercard International Incorporated (MasterCard Incorporated)
• Inventors: McGeehan, Thomas, Merz, Christopher J.
• Granted Patent: US 7,925,652 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24558 Binary matching operations
• CPC Class Codes: G06F 16/90344 by using string matching techniques

Abstract

A computer-based method for character string matching of a candidate character string with a plurality of character string records stored in a database is described. The method includes a) identifying a set of reference character strings in the database, the reference character strings identified utilizing an optimization search for a set of dissimilar character strings, b) generating an n-gram representation for one of the reference character strings in the set of reference character strings, c) generating an n-gram representation for the candidate character string, d) determining a similarity between the n-gram representations, e) repeating steps b) and d) for the remaining reference character strings in the set of identified reference character strings, and f) indexing the candidate character string within the database based on the determined similarities between the n-gram representation of the candidate character string and the reference character strings in the identified set.

Claims

1. A computer-based method for character string matching of a candidate character string with a plurality of character string records stored within a database, said method comprising:

a) identifying a set of reference character strings in the database, the reference character strings identified utilizing an optimization search for a set of dissimilar character strings;

b) generating an n-gram representation for one of the reference character strings in the set of reference character strings;

c) generating an n-gram representation for the candidate character string;

d) determining a similarity between the n-gram representations;

e) repeating steps b) and d) for the remaining reference character strings in the set of identified reference character strings; and

f) indexing the candidate character string within the database based on the determined similarities between the n-gram representation of the candidate character string and the n-gram representation of the reference character strings in the identified set.

2. A computer-based method according to claim 1 wherein determining a similarity between the n-gram representations comprises:

computing a two-dimensional vector containing a frequency of occurrence of all unique n-grams in the candidate character string and a frequency of occurrence of all unique n-grams in the reference character string; and

computing a similarity metric for the candidate character string, with respect to the reference character string, based on the two-dimensional vector.

3. A computer-based method according to claim 2 wherein computing a similarity metric for the candidate character string comprises using a structured query language calculation to compare contents of the two-dimensional vector.

4. A computer-based method according to claim 2 wherein computing a similarity metric comprises:

determining a magnitude of the vector associated with the candidate character string as magnitude A;

determining a magnitude of the vector associated with the reference character string as magnitude B;

computing a dot product between the two vectors; and

computing the similarity metric according to (dot product/(magnitude A×

magnitude B)).

5. A computer-based method according to claim 2 wherein computing a similarity metric comprises implementing an n-gram frequency similarity calculation in ASCII structured query language.

6. A computer-based method according to claim 5 further comprising using the n-gram frequency similarity computation to form a binary key that indicates a similarity between the candidate character string and each of the identified reference character strings.

7. A computer-based method according to claim 1 wherein indexing the candidate character string within the database comprises:

implementing an n-gram frequency similarity calculation;

using the calculation to form binary keys that indicates a similarity between a record associated with the candidate character string and records associated with each of the identified reference character strings;

joining records that share the same binary key value; and

sorting the joined records by relevance by summing the products of the frequency weights of all matching n-grams.

8. A computer-based method according to claim 1 wherein indexing the candidate character string comprises generating a matrix of similarity metrics for the candidate character string as compared to the set of reference character strings.

9. A computer-based method according to claim 1 wherein indexing the candidate character string comprises:

assigning a binary key corresponding to the reference character string a value of 1 if the similarity metric is above a predefined threshold; and

assigning a binary key corresponding to the reference character string a value of 0 if the similarity metric is below the predefined threshold.

10. A computer-based method according to claim 1 wherein identifying a set of reference character strings in the database comprises using a principal components factor analysis to identify a set of dissimilar character string records.

11. A computer programmed to:

utilize an optimization search to identify a set of dissimilar reference character strings in a database;

generate an n-gram representation for a candidate character string;

generate an n-gram representation for each of the dissimilar reference character strings in the set;

determine a similarity between the n-gram representation of the candidate character string and each n-gram representation of the set of dissimilar reference character strings; and

index the candidate character string within the database based on the similarities determined in the n-gram representations.

12. A computer according to claim 11 wherein to determine a similarity between the n-gram representation of the candidate character string and each n-gram representation of the set of dissimilar reference character strings, said computer is further programmed to

compute two-dimensional vectors containing a frequency of occurrence of all unique n-grams in the candidate character string and all unique n-grams in one of the reference character strings for each of the reference character strings;

and

compute a similarity metric for the candidate character string, with respect to each reference character string, based on the two-dimensional vectors.

13. A computer according to claim 12 wherein to compute the similarity metric, said computer is programmed to utilize a structured query language calculation to compare contents of the two-dimensional vectors.

14. A computer according to claim 11 wherein to index the candidate character string, said computer is programmed to:

assign a binary key corresponding to the reference character string a value of 1 if the determined similarity is above a predefined threshold; and

assign a binary key corresponding to the reference character string a value of 0 if the determined similarity is below the predefined threshold.

15. A computer according to claim 11 wherein to utilize an optimization search, said computer is programmed to use a principal components factor analysis to identify a set of dissimilar reference character strings in the database.

16. A computer-based method for approximate matching of a candidate character string to a set of reference character strings within a database, said method comprising:

individually comparing an n-gram representation of the candidate character string to n-gram representations for each reference character string in the set of reference character strings; and

generating a binary index value that is associated with the candidate character string, the binary index value indicating a similarity between the candidate character string and each of the reference character strings.

17. A computer-based method according to claim 16 wherein individually comparing an n-gram representation of the candidate character string to n-gram representations for each reference character string comprises using a structured query language n-gram frequency similarity calculation to compare the n-gram representations.

18. A computer-based method according to claim 16 wherein individually comparing an n-gram representation of the candidate character string to n-gram representations for each reference character string comprises:

a) determining a magnitude (A) of a vector associated with the n-gram representation of the candidate character string;

b) determining a magnitude (B) of a vector associated with the n-gram representation of one of the reference character strings as magnitude B;

c) computing a dot product between the two vectors; and

d) computing a similarity metric for the candidate character string with respect to the reference character string according to (dot product/(magnitude A x magnitude B)); and

repeating steps b), c), and d) for each reference character string.

19. A computer-based method according to claim 16 wherein the candidate character string is one of a merchant name and a merchant address and the set of reference character strings within the database are, respectively, a larger set of merchant names and merchant addresses.

20. A computer-based method according to claim 16 further comprising:

joining records that share the same binary index value; and

sorting the joined records by relevance by summing the products of the frequency weights of all matching n-gram representations.