System and method for adaptive multi-cultural searching and matching of personal names

• US 6,963,871 B1
• Filed: 03/25/1999
• Issued: 11/08/2005
• Est. Priority Date: 03/25/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: Language Analysis Systems, Inc. (International Business Machines Corporation)
• Inventors: McCallum-Bayliss, Heather, Shaefer, Leonard Arthur Jr., Lutz, Richard D., Hermansen, John Christian
• Primary Examiner(s): Corrielus, Jean M.
• Assistant Examiner(s): HWANG, JOON H
• Application Number:
  US09/275,766
• Time in Patent Office: 2,420 Days
• Field of Search: 707 1- 10, 707100-1041, 707/532, 707/536, 704 1- 10, 704/258
• US Class Current: 1/1
• CPC Class Codes: G06F 16/33 Querying
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

An automated name searching system incorporates an automatic name classifier and a multi-path architecture in which different algorithms are applied based on cultural identity of the query name. The name classifier operates with a preemptive list, analysis of morphological elements, length, and linguistic rules. A name regularizer produces a character based computational representation of the name. A pronunciation equivalent representation such as an IPA language representation, and language specific rules to generate name searching keys, are used in a first pass to eliminate database entries which are obviously not matches for the query name. The methods can also be implemented as a callable set of library routines including an intelligent preprocessor and a name evaluator that produces a score comparing a query name and database name, based on a variety of user-adjustable parameters. The user-controlled parameters permit tuning of the search methodologies for specific custom applications.

Claims

1. A computer-implemented method of comparing input names and a stored names, the method comprising:

accessing an input name of a particular human culture;

accessing a stored name of the particular human culture;

selecting a first linguisitic algorithm that is based on the stored name and other names in the particular human culture, wherein the first linguistic algorithm is based on one or more linguistic features including one or more of phonological features, orthographic features, semantic features, syntactic features, n-gram based features, the number of elements in names, the types of elements in names, variations in spelling of a name, accounting for exclusion of expected information in a name, positional information of names, inclusion of additional information in a name, and whether surnames match;

selecting a second linguistic algorithm, different from the first linguistic algorithm, that is based on the stored name and other names in the particular human culture, wherein the second linguistic algorithm is based on one or more linguistic features including one or more of phonological features, orthographic features, semantic features, syntactic features, n-gram based features, the number of elements in names, the types of elements in names, variations in spelling of a name, accounting for exclusion of expected information in a name, positional information of names, inclusion of additional information in a name, and whether surnames match, wherein the first linguistic algorithm and the second linguistic algorithm are based on different linguistic features of the particular human culture;

comparing the input name and the stored name using the first linguistic algorithm;

comparing the input name and the stored name using the second linguistic algorithm; and

providing a non-binary indication of whether the input name matches the stored name base on (i) the comparing of the input name and the stored name using the first linguistic algorithm and (ii) the comparing of the input name and the stored name using the second linguistic algorithm.

2. The method of claim 1 wherein selecting the first linguistic algorithm comprises:

selecting a set of algorithms based on names in the particular culture, the set of algorithms being selected from among multiple sets of algorithms, each set of algorithms being based on names in a different culture; and

selecting the first linguistic algorithm from the set of algorithms.

3. The method of claim 1 wherein selecting the first linguistic algorithm comprises selecting the first linguistic algorithm from among multiple algorithms, each algorithm being based on names in a different culture.

4. The method of claim 1 wherein providing the indication comprises providing an indication that the input name matches the stored name.

5. The method of claim 1 further comprising:

accessing a second stored name of the particular culture;

comparing the input name and the second stored name using the first linguistic algorithm; and

providing an indication of whether the input name matches the second stored name based on the comparing of the input name and the second stored name.

6. The method of claim 5 wherein:

providing the indication of whether the input name matches the stored name comprises providing an indication that the input name matches the stored name, and

providing the indication of whether the input name matches the second stored name comprises providing an indication that the input name matches the second stored name.

7. The method of claim 5 wherein:

comparing the input name and the stored name comprises producing a score indicating likelihood of the input name matching the stored name, and

comparing the input name and the second stored name comprises producing a second score indicating likelihood of the input name matching the second stored name.

8. The method of claim 7 further comprising ranking the stored name and the second stored name based on the score and the second score.

9. The method of claim 1 wherein comparing the input name and the stored name comprises segmenting the input name into different types of elements, the segmenting being based on the particular culture.

10. The method of claim 9 wherein segmenting the input name is based on a space in the input name.

11. The method of claim 9 wherein segmenting the input name contributes to a determination of where a space should appear in the input name.

12. The method of claim 9 wherein comparing the input name and the stored name further comprises assigning a weight to an element of the input name based on the particular culture and based on a type of the element, the weight indicating a relative amount of identifying information expected to be contained in the element.

13. The method of claim 12 wherein assigning the weight comprises assigning a relatively low weight to the element.

14. The method of claim 13 wherein the element comprises a title.

15. The method of claim 13 wherein the element comprises an affix.

16. The method of claim 13 wherein the element comprises a qualifier.

17. The method of claim 1 wherein the first linguistic algorithm is based on a naming convention in the particular culture, and comparing comprises comparing using the first linguistic algorithm that is based on the naming convention.

18. The method of claim 17 wherein the naming convention includes information on which name element has the most valuable identifying information.

19. The method of claim 18 wherein the naming convention identifies the last of multiple surnames as having the most valuable identifying information.

20. The method of claim 1 wherein comparing comprises producing a score indicating likelihood of the input name matching the stored name.

21. The method of claim 20 wherein providing the indication comprises providing the score.

22. The method of claim 21 wherein providing the score comprises providing the score to a user.

23. The method of claim 20 wherein the score is non-binary.

24. The method of claim 20 wherein the score indicates a partial match between the input name and the stored name.

25. The method of claim 2 wherein comparing the input name and the stored name using the first linguistic algorithm comprises comparing phonological similarity of the input name and the stored name.

26. The method of claim 1 wherein comparing the input name and the stored name using the first linguistic algorithm comprises comparing orthographic similarity of the input name and the stored name.

27. The method of claim 26 wherein comparing the input name and the stored name using the first linguistic algorithm comprises performing an n-gram analysis of the input name and the stored name.

28. The method of claim 27 wherein performing the n-gram analysis comprises performing a digram analysis.

29. The method of claim 27 wherein performing the n-gram analysis considers position of n-grams within the input name and the stored name.

30. The method of claim 1 wherein comparing the input name and the stored name using the first linguistic algorithm comprises comparing syntax of elements of the input name and elements of the stored name.

31. The method of claim 1 wherein comparing the input name and the stored name using the first linguistic algorithm comprises comparing semantic equivalence of the input name and the stored name.

32. The method of claim 1 wherein comparing the input name and the stored name using the first linguistic algorithm comprises comparing discrepancy in number of elements of the input name and the stored name.

33. The method of claim 1 wherein comparing the input name and the stored name using the first linguistic algorithm comprises accounting for variations in spelling of the input name of the stored name.

34. The method of claim 1 wherein comparing the input name and the stored name using the first linguistic algorithm comprises accounting for exclusion of expected information in the input name or the stored name.

35. The method of claim 1 wherein comparing the input name and the stored name using the first linguistic algorithm comprises comparing positional information of the input name and the stored name.

36. The method of claim 1 wherein comparing the input name and the stored name using the first linguistic algorithm comprises accounting for inclusion of additional information in the input name or the stored name.

37. The method of claim 1 wherein:

comparing the input name and the stored name comprises determining whether surnames of the input name and the stored name match, and

providing the indication comprises providing an indication that the input name does not match the stored name if surnames of the input name and the stored name do not match.

38. The method of claim 1 wherein:

the input name is a predictable variation of the stored name, and

providing the indication comprising providing an indication that the input name matches the stored name.

39. The method of claim 1 wherein:

the input name is a random variation of the stored name, and

providing the indication comprising providing an indication that the input name matches the stored name.

40. The method of claim 1 wherein:

the input name includes a first element randomly varied from the stored name and a second element predictably varied from the stored name, and

providing the indication comprising providing an indication that the input name matches the stored name.

41. The method of claim 1 wherein comparing the input name and the stored name is based on a user-configurable parameter.

42. The method of claim 1 wherein accessing the stored name comprises accessing a name that is stored in volatile memory.

43. An apparatus comprising a computer readable medium having instructions stored thereon that when executed by a machine result in at least the following:

accessing an input name of a particular human culture;

accessing a stored name of the particular human culture;

selecting a first linguistic algorithm that is based on the stored name and other names in the particular human culture, wherein the first linguistic algorithm is based on one or more linguistic features including one or more of phonological features, orthographic features, semantic features, syntactic features, n-gram based features, the number of elements in names, the types of elements in names, variations in spelling of a name, accounting for exclusion of expected information in a name, positional information of names, inclusion of additional information in a name, and whether surnames match;

selecting a second linguistic algorithm, different from the first linguistic algorithm, that is based on the stored name and other names in the particular human culture, wherein the second linguistic algorithm is based on one or more linguistic features including one or more of phonological features, orthographic features, semantic features, syntactic features, n-gram based features, the number of elements in names, the types of elements in names, variations in spelling of a name, accounting for exclusion of expected information in a name, positional information of names, inclusion of additional information in a name, and whether surnames match, wherein the first linguistic algorithm and the second linguistic algorithm are based on different linguistic features of the particular human culture;

comparing the input name and the stored name using the first linguistic algorithm;

comparing the input name and the stored name using the second linguistic algorithm; and

providing a non-binary indication of whether the input name matches the stored name based on (i) the comparing of the input name and the stored name using the first linguistic algorithm and (ii) the comparing of the input name and the stored name using the second linguistic algorithm.