Name finding system and method

• US 7,877,375 B1
• Filed: 03/29/2007
• Issued: 01/25/2011
• Est. Priority Date: 03/29/2007
• Status: Active Grant

• Current Assignee: OCLC Online Computer Library Center Incorporated
• Original Assignee: OCLC Online Computer Library Center Incorporated
• Inventors: LeVan, Ralph Reese
• Primary Examiner(s): HARPER, ELIYAH STONE
• Application Number:
  US11/693,329
• Time in Patent Office: 1,398 Days
• Field of Search: 707/104.1, 707/100, 707/10, 707/713, 707/736, 707/758
• US Class Current: 707/713
• CPC Class Codes: G06F 16/2468 Fuzzy queries
• CPC Class Codes: G06F 40/295 Named entity recognition

Abstract

An improved system and method for name searching. The system and method comprise software routines and a database of names with special indexes to support name-based searches. The special indexes are created using phonetic, nicknames and misspelling algorithms. A software search routine applies progressively fuzzier searches, and ranks the intermediate results according to popularity of names and closeness of names in the query to name records in the database, eliminating unsuitable names, until a predetermined number of candidate names have been found. Highly relevant results are returned even when the user provides incomplete, errant, or exactly matching search queries for the name as indexed. The system and method may be used in any information retrieval system or service that indexes and presents names in search results.

Claims

1. A computerized method for optimizing name search results for a computer user comprising:

(a) creating at a computer for a name database indices comprising;

(i) a phonetic index with terms generated from application of at least one phonetic algorithm to first names and to last names in said database;

(ii) a nickname index with terms generated from application of at least one nickname algorithm to first names in said database;

(b) creating at said computer for said name database a misspelling index with keys for finding names in said database by applying a misspelling algorithm to first names and to last names wherein the algorithm;

(i) alphanumerically sorts the letters in said first names and last names;

(ii) generates a first key for each of said first names and said last names comprising letters for said first name or last name in alphanumeric sorted order; and

(iii) removes each letter of said first name or last name in alphanumeric sorted order to generate additional keys comprising said first key with said letters removed from said first key;

(c) receiving at said computer a search request comprising a first name and a last name;

(d) receiving at said computer a candidate number of names from said database;

(e) creating at said computer a search results set by adding names to said search results set for said first name and said last name up to said candidate number of names according to the following steps;

(i) searching said name database for an exact match of said first name and said last name;

(ii) searching said name database for names that have all words from said last name and said first name but not in said search results set;

(iii) searching said name database for names that have all words from said last name and a fuzzy version of said first name using said phonetic, nickname, and misspelling indices but not in said search results set;

(iv) searching said name database for names that have all words from said first name and a fuzzy version of said last name using said phonetic and misspelling indices but not in said search results set;

(v) searching said name database for names that have fuzzy versions of said first name and said last name using said phonetic, misspelling, and nickname indices but not in said search results set;

(vi) ranking intermediate results at each step (i)-(v) and eliminating a plurality of names from said search results set according to said rankings for said names; and

(f) presenting to said computer user on a computer display names from said search results set up to said candidate number of names.

2. The method of claim 1 wherein said names in said database are normalized, case shifted words.

3. The method of claim 1 wherein said phonetic algorithm is selected from the group consisting of the Soundex algorithm and the Daitch-Mokotoff Soundex algorithm.

4. The method of claim 1 wherein said nicknames algorithm comprises the following steps:

(a) preparing a text file of formal names and nicknames;

(b) inverting said file such that nicknames map to formal names and to nicknames for said formal names; and

(c) generating multiple keys for first names for all possible nicknames and formal names related to said first names.

5. The method of claim 1 wherein ranking intermediate results comprises:

(a) ranking said names in said search results set by popularity; and

(b) ranking said names in said search results set according to closeness of said first name and said last name to name records in said database.

14. The method of claim 1 wherein said nicknames algorithm comprises the following steps:

(i) preparing a text file of formal names and nicknames;

(ii) inverting said file such that nicknames map to formal names and to nicknames for said formal names; and

(iii) generating multiple keys for first names for all possible nicknames and formal names related to said first names.

17. The method of claim 1 wherein receiving at said computer a search request comprising a first name and a last name comprises receiving a search request comprising a misspelled first name or last name.

6. A computerized system for presenting to a computer user optimized name search results comprising:

(a) a name database at a computer with a plurality of indexes comprising;

(i) a phonetic index with terms generated from application of at least one phonetic algorithm to first names and last names in said database;

(ii) a nickname index with terms generated from application of at least one nickname algorithm to first names in said database;

(iii) a misspelling index with terms generated from application of at least one misspelling algorithm to first names and last names in said database wherein said algorithm;

(A) alphanumerically sorts letters for each of said first names and last names;

(B) generates a first key for each of said first names and said last names comprising letters for said first name or last name in alphanumeric sorted order;

(B) removes each letter of said first name or last name in alphanumeric sorted order to generate additional keys comprising said first key with said letters removed from said first key;

(b) memory at said computer for storing a search results set created at said computer by adding names to said search results set for a first name and a last name search request up to a candidate number of names from said database, said search results set created according to the following steps;

(i) searching said name database for an exact match of said first name and said last name;

(ii) searching said name database for names that have all words from said last name and said first name but not in said search results set;

(iii) searching said name database for names that have all words from said last name and a fuzzy version of said first name using said phonetic, nickname, and misspelling indices but not in said search results set;

(iv) searching said name database for names that have all words from said first name and a fuzzy version of said last name using said phonetic and misspelling indices but not in said search results set;

(v) searching said name database for names that have fuzzy versions of said first name and said last name using said phonetic, nickname, and misspelling indices but not in said search results set;

(vi) ranking said intermediate results at each step (i)-(v) and eliminating a plurality of names from said search results set according to said rankings for said names; and

(c) a computer display for presenting to said computer user names from said search results set up to said candidate number of names.

7. The system of claim 6 wherein said names in said database are normalized, case shifted words.

8. The system of claim 6 wherein said phonetic algorithm is selected from the group consisting of the Soundex algorithm and the Daitch-Mokotoff Soundex algorithm.

9. The system of claim 6 wherein said nicknames algorithm comprises the following steps:

(a) preparing a text file of formal names and nicknames;

(b) inverting said file such that nicknames map to formal names and to nicknames for said formal names; and

(c) generating multiple keys for first names for all possible nicknames and formal names related to said first names.

10. The system of claim 6 wherein ranking intermediate results comprises:

(a) ranking said names in said search results set by popularity; and

(b) ranking said names in said search results set according to closeness of said first name and said last name to name records in said database.

18. The system of claim 6 wherein said first name and last name search request comprises a misspelled first name or last name.

11. A computerized method for optimizing name search results for a computer user comprising:

(a) creating at a computer for a name database a phonetic index with terms generated from application of at least one phonetic algorithm to first names and to last names in said database;

(b) creating at said computer for said name database a nickname index with terms generated from application of at least one nickname algorithm to first names in said database;

(c) creating at said computer for said name database a misspelling index with terms generated by applying a misspelling algorithm to first names and to last names wherein said misspelling algorithm generates;

(i) a first key for each of said first names and said last names comprising letters for said first name or last name in alphanumeric sorted order; and

(ii) for each letter of said first name or last name, an additional generated key comprising said first key with said letter removed from said first key;

(d) receiving at said computer a search request comprising a first name and a last name;

(e) receiving at said computer a candidate number of names from said database;

(f) creating at said computer a search results set by adding names to said search results set for said first name and said last name up to said candidate number of names according to the following steps;

(i) searching said name database for an exact match of said first name and said last name;

(ii) searching said name database for names that have all words from said last name and said first name and that are not in said search results set;

(iii) searching said name database for names that have a fuzzy version of said last name and said first name using said phonetic, nickname, and misspelling indices and that are not in said search results set;

(iv) ranking intermediate results at each step (i)-(iii) and eliminating a plurality of names from said search results set according to said rankings for said names; and

(g) presenting on a computer display names from said search results set up to said candidate number of names.

12. The method of claim 11 wherein said names in said database are normalized, case shifted words.

13. The method of claim 11 wherein said phonetic algorithm is selected from the group consisting of the Soundex algorithm and the Daitch-Mokotoff Soundex algorithm.

15. The method of claim 11 wherein ranking intermediate results comprises:

(i) ranking said names in said search results set by popularity; and

(ii) ranking said names in said search results set according to closeness of said first name and said last name to names in said database.

16. The method of claim 11 wherein receiving at said computer a search request comprising a first name and a last name comprises receiving a search request comprising a misspelled first name or last name.