Computational Techniques for Improved Name Search

COMPUTATIONAL TECHNIQUES FOR IMPROVED NAME SEARCH Beatrice T. Oshika SPARTA, Inc. 2560 Ninth Street Suite 315B Berkeley, CA 94710 Bruce Evans TRW MS 02/1761 One Space Park Redondo Beach, CA 90278 Filip Machi Department of Mathematics University of California, Berkeley Berkeley, CA 94720 Janet Tom Santa Monica Research Center Unisys 2400 Colorado Avenue Santa Monica, CA 94710 ABSTRACT This paper describes enhancements made to techniques currently used to search large databases of proper names. Improvements included use of a Hidden Markov Model (HMM) statistical classifier to identify the likely linguistic provenance of a surname, and application of language-specific rules to generate plausible spelling variations of names. These two components were incorporated into a prototype front-end system driving existing name search procedures. HMM models and sets of linguistic rules were constructed for Farsi, Spanish and Vietnamese surnames and tested on a database of over 11,000 entries. Preliminary evaluation indicates improved retrieval of 20-30% as measured by number of correct items retrieved. 1.0 INTRODUCTION This paper describes enhancements made to current name search techniques used to access large databases of proper names. The work focused on improving name search algorithms to yield better matching and retrieval performance on data-bases containing large numbers of non-European 'foreign' names. Because the linguistic mix of names in large computer-supported databases has changed due to recent immigration and other demographic factors, current name search procedures do not provide the accurate retrieval required by insurance companies, state motor vehicle bureaus, law enforcement agencies and other institutions. As the potential consequences of incorrect retrieval are so severe (e.g., loss of benefits, false arrest), it is necessary that name name search techniques be improved to handle the linguistic variability reflected in current databases. Our specific approach decomposed the name • search problem into two main components: Language classification techniques to identify the source language for a given query name, and Name association techniques, once a source language for a name is known, to exploit language-specific rules to generate variants of a name due to spelling variation, bad transcrip- tions, nicknames, and other name conventions. A statistical classification technique based on the use of Hidden Markov Models (HMM) was used as a language discriminator. The test database contained about 11,000 names, including about 2,000 each from three target languages, Vietnamese, Farsi and Spanish, and 5,000 termed 'other' to broadly represent general European names. The decision procedures assumed a closed-world situation in which a name must be assigned to one of the four classes. Language-specific rules in the form of context-sensitive, string rewrite rules were used to generate name variants. These were based on linguistic analysis of naming conventions, pronunciations and common misspellings for each target language. These two components were incorporated into a front-end system driving existing name search procedures. The front-end system was implemented in the C language and runs on a VAX-11/780 and Sun 3 workstations under Unix 4.2. Preliminary tests 203 indicate improved retrieval (number of correct items retrieved) by as much as 20-30% over standard SOUNDEX and …

Content truncated to 500 words