Hashing-Based Approaches to Spelling Correction of Personal Names

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 1256–1265, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics Hashing-based Approaches to Spelling Correction of Personal Names Raghavendra Udupa Microsoft Research India Bangalore, India raghavu@microsoft.com Shaishav Kumar Microsoft Research India Bangalore, India v-shaisk@microsoft.com Abstract We propose two hashing-based solutions to the problem of fast and effective personal names spelling correction in People Search applications. The key idea behind our meth- ods is to learn hash functions that map similar names to similar (and compact) binary code- words. The two methods differ in the data they use for learning the hash functions - the first method uses a set of names in a given lan- guage/script whereas the second uses a set of bilingual names. We show that both methods give excellent retrieval performance in com- parison to several baselines on two lists of misspelled personal names. More over, the method that uses bilingual data for learning hash functions gives the best performance. 1 Introduction Over the last few years, People Search has emerged as an important search service. Unlike general Web Search and Enterprise Search where users search for information on a wide range of topics including peo- ple, products, news, events, etc., People Search is about people. Hence, personal names are used pre- dominantly as queries in People Search. As in gen- eral Web Search, a good percentage of queries in People Search is misspelled. Naturally, spelling cor- rection of misspelled personal names plays a very important role in not only reducing the time and ef- fort needed by users to find people they are search- ing for but also in ensuring good user experience. Spelling errors in personal names are of a differ- ent nature compared to those in general text. Long before People Search became widely popular, re- searchers working on the problem of personal name matching had recognized the human tendency to be inexact in recollecting names from the memory and specifying them. A study of personal names in hospital databases found that only 39% of the er- rors in the names were single typographical errors (Friedman and Sideli, 1992)1. Further, multiple and long distance typographical errors (Gregzorz Kon- drak for Grzegorz Kondrak), phonetic errors (as in Erik Bryl for Eric Brill), cognitive errors (as in Sil- via Cucerzan for Silviu Cucerzan) and word substi- tutions (as in Rob Moore for Bob Moore) are ob- served relatively more frequently in personal names compared to general text. In addition to within-the-word errors, People Search queries are plagued by errors that are not usually seen in general text. The study by Fried- man and Sideli discovered that 36% of the errors were due to addition or deletion of a word (as in Ricardo Baeza for Ricardo Baeza-Yates) (Friedman and Sideli, 1992). Although word addition and dele- tion generally do not come under the purview of spelling correction, in People Search they are im- portant and need to be addressed. Standard approaches to …

Content truncated to 500 words