Hashing-Based Approaches to Spelling Correction of Personal Names

Raghavendra Udupa, Shaishav KumarEMNLP 2010

Abstract

This paper presents two novel hashing-based methods, M-HASH and B-HASH, designed to correct misspelled personal names in large-scale "People Search" applications. By learning hash functions that map similar names to compact binary codewords, these methods enable high-accuracy retrieval across millions of records in milliseconds. Experimental results demonstrate that the bilingual approach (B-HASH), which leverages transliteration pairs, significantly outperforms traditional phonetic and search engine baselines, achieving over 92% precision on Wikipedia-based datasets.

1. Introduction

Standard spell-checkers are optimized for general text where context helps resolve ambiguity. However, searching for names in directories (e.g., corporate intranets or social networks) presents unique challenges. Name queries often lack context, follow distinct error patterns (phonetic slips, cognitive errors), and must be processed against millions of records in real-time. Traditional string-matching algorithms like Edit Distance are computationally prohibitive at this scale, while many applications lack the massive query logs required to train web-scale error models.

2. Methodology

The authors propose a two-stage search pipeline consisting of NAME_BUCKETING for fast candidate generation and NAME_MATCHING for rigorous re-ranking. The core innovation lies in the learned hash functions:

  • M-HASH (Monolingual Hashing): This method treats name similarity as a graph problem. Using a graph Laplacian, it ensures that names with small edit distances are mapped to binary codewords with small Hamming distances.
  • B-HASH (Bilingual Hashing): This approach leverages transliteration pairs (e.g., English-Hindi). By applying Canonical Correlation Analysis (CCA), the model projects names from different scripts into a shared binary space. This forces the model to capture the phonetic "essence" of a name, making it highly robust against spelling variations.

For the final matching stage, a logistic function combines Damerau-Levenshtein edit distance with the Hamming distance of the learned codewords to produce a final similarity score.

3. Experimental Results

The methods were evaluated on two datasets: DUMBTIONARY (550,000 Wikipedia names) and INTRANET (150,000 corporate names with "hard" misspelling cases).

3.1 Accuracy and Baseline Comparison

B-HASH emerged as the superior model. On the DUMBTIONARY set, it achieved a Precision@1 of 92.53%, significantly outperforming traditional phonetic algorithms like Double Metaphone (DM) and search baselines like BM25.

Table 1: Performance comparison of hashing methods against phonetic and search baselines on the DUMBTIONARY dataset.

3.2 Robustness and Scaling

On the more challenging INTRANET dataset, where average edit distances were higher, B-HASH maintained strong performance. The researchers found that B-HASH's accuracy improved as the size of the bilingual training set increased, reaching 77.79% accuracy with 15,000 training pairs, compared to just 54% for Double Metaphone.

Table 2: Accuracy of B-HASH vs. M-HASH on the INTRANET dataset as a function of training set size.

3.3 Efficiency

B-HASH also demonstrated superior computational efficiency. In the Wikipedia directory, B-HASH processed queries in an average of 87ms, compared to 190ms for M-HASH. This speedup is attributed to B-HASH producing fewer "collisions" or irrelevant candidates during the bucketing stage.

4. Discussion and Conclusion

A key insight of this research is that bilingual data acts as a powerful "noise filter." Training on transliteration pairs forces the model to learn phonetic invariants that are highly effective for catching human spelling errors in a single language. While the current work focuses on English-Hindi pairs, the methodology is extensible to other conjugate languages. Future work will explore combining monolingual and bilingual data into a single, unified model to further enhance robustness across diverse linguistic contexts.

Summary updated

BibTeX
@inproceedings{udupa2010hashing,
  author = {Raghavendra Udupa and Shaishav Kumar},
  title = {{Hashing-Based Approaches to Spelling Correction of Personal Names}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2010},
}
Figure