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.
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.
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