Configurable search tool for finding and scoring non-exact matches in a relational database

• US 7,155,427 B1
• Filed: 10/30/2002
• Issued: 12/26/2006
• Est. Priority Date: 10/30/2002
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Chow, Carol, Kocher, Charity D., Pandey, Jyoti, Rangan, Srinivasa, Prothia, Gautam, Fothergill, Alan
• Primary Examiner(s): Wong, Don
• Assistant Examiner(s): LU, CHARLES EDWARD
• Application Number:
  US10/285,029
• Time in Patent Office: 1,518 Days
• Field of Search: 707/1, 707/3, 707/4, 707/5, 704/9, 704/231, 704/235, 704/251
• US Class Current: 707/694
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A computer-implemented method of searching for exact and non-exact matches in a first database includes steps of transforming and standardizing values of selected attributes stored in the first database according to selected first transformation functions while maintaining the first database unchanged; storing the transformed and standardized values of the selected attributes in a second database that is separate from the first database; providing an input record against which to compare contents of the second database; transforming and standardizing values of selected attributes of the provided input record according to selected second transformation functions, and searching only the second database for at least one of exact and non-exact matches to the transformed and standardized values of the selected attributes of the input record according to selected match rules.

Claims

1. A computer-implemented method of searching for exact and non-exact matches in a first database, comprising the steps of:

transforming and standardizing values of selected attributes stored in the first database according to selected first transformation functions while maintaining the first database unchanged;

storing the transformed and standardized values of the selected attributes in a second database that is separate from the first database;

providing an input record against which to compare contents of the second database;

transforming and standardizing values of selected attributes of the provided input record according to selected second transformation functions;

searching only the second database for at least one of exact and non-exact matches to the transformed and standardized values of the selected attributes of the input record according to selected match rules, and

assigning a score to each of the at least one exact and non-exact matches, the score assigning step including assigning a percentage weight to each of the first transformation functions.

2. The method of claim 1, wherein the first transformation functions are the same as the second transformation functions.

3. The method of claim 1, wherein the first transformation functions includes at least one of the following steps:

removing non-alpha numeric characters;

removing vowels;

removing selected noise words;

removing double letters, and

converting to upper case.

4. The method of claim 1, wherein the first transformation functions include replacing at least one word of values of selected attributes stored in the first database with a replacement word.

5. The method of claim 4, wherein the replacement word is stored in a replacement table that maps variations of a selected word onto a standardized version of the selected word.

6. The method of claim 1, wherein the selected match rules include scoring criteria and wherein the score is assigned to each of the at least one exact and non-exact matches according to the scoring criteria.

7. The method of claim 6, further comprising the step of providing the at least one of exact and non-exact matches according to the assigned score.

8. The method of claim 1, wherein the searching step includes a step of returning a set of at least one potential matching record within the second database, the at least one potential matching record of the set containing attributes that match the transformed and standardized values of the selected attributes of the provided input record.

9. The method of claim 8, wherein the selected match rules include scoring criteria and wherein the method further includes a step assigning the score to each record of the returned set according to the scoring criteria.

10. The method of claim 9, further including weighting the assigned score by a selected weight.

11. The method of claim 9, further including a step of comparing the score assigned to each record of the returned set against a selected threshold and returning as matches only those records of the returned set having assigned scores above the selected threshold.

12. The method of claim 1, wherein, for non-exact matches, the method further comprises the step of determining an extent of similarity between the transformed and standardized values of the selected attributes of the provided input record and values of the corresponding attributes in the second database.

13. The method of claim 12, wherein the extent of similarity is determined by:

determining an edit distance between the non-exact matches and the transformed and standardized values of the selected attributes of the provided input record, the edit distance being equal to a number of changes required to make the non-exact matches match the transformed and standardized values of the selected attributes of the provided input record exactly;

subtracting the edit distance from a number of characters in a longest one of the non-exact matches;

dividing a result of the subtracting step by a number of characters in a longest one of the non-exact matches, and

expressing a result of the dividing step as an integer.

14. The method of claim 1, further including a step of maintaining the second database in synchronism with the first database.

15. A computer-implemented method of maintaining records in a first database, the first database storing a plurality of attributes, the method comprising:

a first transforming and standardizing step to transform and standardize values of selected attributes stored in the first database according to first transformation and standardization functions while maintaining the first database unchanged;

a storing step to store the transformed and standardized attribute values in a second database that is separate from the first database;

a providing step to provide an input record against which to compare contents of the second database;

a second transforming and standardizing step to transform and standardize values of the attributes of the provided input record according to second transformation and standardization functions;

an applying step to apply match rules to compare the standardized attribute values of the provided input record to the standardized attribute values stored in the second database, and to identify a set of potential duplicate records based upon results of the application of the match rules;

scoring the set of potential duplicate records, the scoring step including a step of assigning a percentage weight to each of the first transformation functions, and

carrying out one of;

merging the provided input record with the at least one record of the set of potential duplicate records; and

preventing the provided input record from being incorporated in the first database.

16. The method of claim 15, wherein the first and second transforming and standardizing steps apply identical transformation functions to the attribute values of the attributes stored in the database and to corresponding attribute values of the provided input record.

17. The method of claim 15, wherein the assigned weight is dependent upon a degree of similarity between the transformed and standardized attribute values and corresponding values stored in the first database.

18. A database system, comprising:

a first database that stores attributes and corresponding values of the attributes;

first means for reading, transforming and standardizing the attribute values stored in the first database according to selected first transformation functions such that an effect of typographical errors and variations in the stored attribute values is minimized, the first means maintaining the first database unchanged;

a second database coupled to the first means, the second database storing the transformed and standardized attribute values, and

second means for searching only the second database for exact and non-exact matches to an input record or for duplicates according to selected match rules, wherein the selected match rules include scoring criteria and wherein a score is assigned to each of the at least one exact and non-exact matches according to the scoring criteria, and wherein the second means is further configured to assign a percentage weight to each of the first transformation functions.

19. The database system of claim 18, further including means for maintaining the second database in synchronism with the first database.

20. The database system of claim 18, wherein the first means is configured to carry out at least one of the following steps on the values of the attributes:

removing non-alpha numeric characters;

removing vowels;

removing selected noise words;

removing double letters, and

converting to upper case.

21. The database system of claim 18, wherein the first means is configured to replace at least one word of values of selected attributes stored in the first database with a replacement word.

22. The database system of claim 21, wherein the replacement word is stored in a replacement table that maps variations of a selected word onto a standardized version of the selected word.

23. The database system of claim 18, wherein the second means is further configured to return a set of at least one potential matching record within the second database, the at least one potential matching record of the set containing attributes that match the transformed and standardized values of the selected attributes of the provided input record.

24. The database system of claim 23, wherein the selected match rules include scoring criteria and wherein the second means is further configured to assign the score to each record of the returned set according to the scoring criteria.

25. The database system of claim 18, wherein, for non-exact matches, the second means is further configured to determine an extent of similarity between the transformed and standardized values of the selected attributes of the provided input record and values of the corresponding attributes in the second database.

26. The database system of claim 25, wherein the extent of similarity is determined by:

determining an edit distance between the non exact matches and the transformed and standardized values of the selected attributes of the provided input record, the edit distance being equal to a number of changes required to make the non-exact matches match the transformed and standardized values of the selected attributes of the provided input record exactly;

subtracting the edit distance from a number of characters in a longest one of the non-exact matches;

dividing a result of the subtracting step by a number of characters in a longest one of the non-exact matches, and

expressing a result of the dividing step as an integer.