Inducing Search Keys for Name Filtering

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 906–914, Prague, June 2007. c⃝2007 Association for Computational Linguistics Inducing Search Keys for Name Filtering L. Karl Branting The MITRE Corporation 7467 Ridge Road, Suite 140 Hanover, MD 21076, U.S.A. lbranting@mitre.org Abstract This paper describes ETK (Ensemble of Transformation-based Keys) a new algo- rithm for inducing search keys for name filtering. ETK has the low computational cost and ability to filter by phonetic sim- ilarity characteristic of phonetic keys such as Soundex, but is adaptable to alternative similarity models. The accuracy of ETK in a preliminary empirical evaluation suggests that it is well-suited for phonetic filtering applications such as recognizing alternative cross-lingual transliterations. 1 Introduction The task of name matching—recognizing when two orthographically distinct strings are likely to denote the same individual—occurs in a wide variety of im- portant applications, including law enforcement, na- tional security, and maintenance of government and commercial records. Coreference resolution, speech understanding, and detection of aliases and duplicate names all require name matching. The orthographic variations that give rise to the name-matching task can result from a variety of fac- tors, including transcription and OCR errors, and spelling variations. In many applications, cross- lingual transliterations are a particularly important source of variation. For example, romanized Ara- bic names are phonetic transcriptions of sounds that have no direct equivalent in English, e.g., “Mo- hamed” or “Muhammet” are two of many possible transliterations for the same Arabic name. Name matching can be viewed as a type of range query in which the input is a set of patterns (such as names on an immigration-control watch list), a collection of text strings (such as a passenger list), a distance metric for calculating the degree of relevant dissimilarity between pairs of strings, and a match threshold expressing the maximum allowable dis- tance between matching names. The goal is to find all text/pattern pairs whose distance under the metric is less than or equal to the threshold. In the simplest case, patterns and the text strings with which they are matched are both individual words. In the gen- eral case, the text may not be segmented into strings corresponding to possible names. Distance metrics for name matching are typically computationally expensive. For example, determin- ing the edit distance between two strings of length n and m requires, in the general case, nm steps. Met- rics based on algorithms that learn from examples of strings that should match (Bilenko et al., 2003; Ristad and Yianilos, 1998) and metrics that use pho- netic similarity criterion, e.g., (Kondrak, 2000) are no less expensive than edit distance. The computational expense of distance metrics means that tractable name matching on large texts typically requires an inexpensive, high-recall filter- ing step to find a subset of the original text to which the expensive similarity metric will be ap- plied. Desiderata for filtering include the following: 1. High recall. The recall of the entire name- matching process is …

Content truncated to 500 words