Methods and systems for implementing approximate string matching within a database

• US 8,219,550 B2
• Filed: 03/04/2011
• Issued: 07/10/2012
• Est. Priority Date: 12/31/2007
• Status: Active Grant

• Current Assignee: Mastercard International Incorporated (MasterCard Incorporated)
• Original Assignee: Mastercard International Incorporated (MasterCard Incorporated)
• Inventors: Merz, Christopher J., McGeehan, Thomas
• Primary Examiner(s): VO, TRUONG V
• Application Number:
  US13/041,075
• Publication Number:
  US 20110167060A1
• Time in Patent Office: 494 Days
• Field of Search: None
• US Class Current: 707/727
• 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:

selecting one or more of the character strings in the plurality of character string records to form a set of reference character strings using a principal components factor analysis (PCFA) to identify a set of dissimilar reference character strings in the plurality of character string records;

generating a binary index key for each of the character strings in the set of character strings, the binary index key comprising a plurality of bits of binary information, each bit indicating a degree of matching of the character string to the set of reference character strings;

generating a binary index key for the candidate character string;

determining a set of character string records stored within the database that include a binary index key that exactly matches the binary index key of the candidate character string;

from the determined set of character string records stored within the database that include a binary index key that exactly matches the binary index key of the candidate character string, locating each character string record whose selected character string matches the respective character string of the candidate string record; and

indexing the candidate character string record within the database based on the matching.

2. A method in accordance with claim 1, wherein generating a binary index key for each of the character strings in the set of character strings comprises comparing an n-gram representation of a selected one of the character strings in the set of character strings and an n-gram representation of each of a set of dissimilar reference character strings, wherein an i-th bit of the binary index key represents a degree of matching of the candidate string with the i-th reference character string.

3. A method in accordance with claim 2, wherein i-th bit in the binary index key is set to a logical 1 if that record matches the i-th reference string above a predetermined threshold.

4. A method in accordance with claim 2, wherein the database is managed by a relational database management system (RDBMS) and wherein generating a binary index key comprises forming the binary index key using a process implemented in the RDBMS to use the n-gram frequency similarity calculation that indicates the similarity of a given record to each of the reference strings identified in the PCFA.

5. A method in accordance with claim 1, further comprising:

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;

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

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;

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

magnitude B)).

6. A method in accordance with claim 5, 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.

7. A method in accordance with claim 5, wherein computing a similarity metric comprises implementing an n-gram frequency similarity calculation in ASCII structured query language.

8. A method in accordance with claim 5, further comprising using the n-gram frequency similarity computation to form a binary index key that indicates a similarity between the candidate character string and each of the identified reference character strings.

9. A method in accordance with claim 1, further comprising identifying a set of dissimilar character strings in the plurality of character string records stored in the database utilizing an optimization search to generate a set of dissimilar reference character strings.

10. A method in accordance with 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 index 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 index key value; and

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

11. A method in accordance with 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.

12. A method in accordance with claim 1, wherein indexing the candidate character string comprises:

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

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

13. A computer database system for matching of a candidate character string with a plurality of character string records stored within a database managed by a relational database management system (RDBMS), said method comprising:

a memory including;

a first data structure including character strings of identification data for a plurality of merchants;

a second data structure including a binary index key representing a similarity of selected character strings to a set of predetermined dissimilar reference strings;

a processor programmed to;

select one or more of the character strings in the first data structure to form the set of predetermined dissimilar reference strings;

generate the binary index key for each of the selected character strings, the binary index key comprising a plurality of bits of binary information, each bit indicating a degree of matching of the character string to the set of reference character strings, the binary index key formed using a process implemented in the RDBMS to use the n-gram frequency similarity calculation that indicates the similarity of a given record to each of the reference strings identified in a principal components factor analysis (PCFA);

generate a binary index key for the candidate character string;

determine a set of character string records stored within the first data structure associated with a binary index key that exactly matches the binary index key of the candidate character string;

from the determined set of character string records stored within the first data structure that include a binary index key that exactly matches the binary index key of the candidate character string, locating each character string record whose selected character string matches the respective character string of the candidate string record; and

index the candidate character string record within the database based on the matching.

14. A system in accordance with claim 13, wherein said processor is further programmed to identify a set of dissimilar character strings in the plurality of character string records stored in the database comprises using a principal components factor analysis to identify a set of dissimilar character string records.

15. A system in accordance with claim 13, wherein said processor is further programmed to compare an n-gram representation of a selected one of the character strings in the set of character strings and an n-gram representation of each of a set of dissimilar reference character strings, wherein an i-th bit of the binary index key represents a degree of matching of the candidate string with the i-th reference character string.

16. A system in accordance with claim 15, wherein i-th bit in the binary index key is set to a logical 1 if that record matches the i-th reference string above a predetermined threshold.

17. A system in accordance with claim 13, wherein said processor is further programmed to identify a set of dissimilar character strings in the plurality of character string records stored in the database utilizing an optimization search to generate a set of dissimilar reference character strings.

18. A system in accordance with claim 13, wherein computing a similarity metric comprises implementing an n-gram frequency similarity calculation in ASCII structured query language.