Abstract
Spelling correction in web search is largely a solved problem due to the availability of massive, aggregated query logs. However, email search presents a unique challenge where "wisdom of the crowd" approaches fail due to data privacy and the highly personalized nature of email content. This paper introduces SpEQ (Spelling for Email Queries), a machine learning framework designed to provide personalized spelling corrections by mining a user’s own mailbox. By leveraging individual context—including contact lists, subject lines, and temporal activity—SpEQ achieves significantly higher accuracy than generic models. Evaluations on the PALIN and ENRON datasets demonstrate that SpEQ achieves up to 97.17% precision, outperforming traditional baselines.
1. Introduction
In the domain of Web Search, spelling correction is highly effective because search engines can analyze billions of query logs to identify common typos and their intended corrections. In contrast, Email Search suffers from two primary hurdles: data scarcity and hyper-personalization.
An individual user’s query history is typically too sparse to provide broad coverage for future typos. Furthermore, email content is private and idiosyncratic; a generic dictionary cannot account for specific colleague names, project-specific jargon, or local geographic references unique to a user's life. For example, a query for "noarvig flies" might be a typo for a colleague named "Norvig" or a reference to the city of "Noorvik," depending entirely on the user's personal context. This paper addresses the challenge of building a robust spelling corrector in the absence of massive global logs, focusing instead on the "small data" available within a user's digital environment.
2. The SpEQ Framework
The authors propose SpEQ, a ranking framework that identifies the most likely intended query ($Q_c$) given a misspelled query ($Q_t$) and its context ($C$). The system operates through a two-stage pipeline:
2.1 Candidate Generation
To ensure computational efficiency, the system first generates a small set of potential corrections (approximately 1,000) directly from the user's mail data. This is achieved using a combination of Dynamic Programming and a scoring function based on Inverse Document Frequency (Idf) and edit distance. This ensures that the candidates are relevant to the specific vocabulary found in the user's inbox.
2.2 Feature-Based Ranking
Once candidates are generated, a machine learning model ranks them using four distinct classes of features:
- Lexical Similarity: Standard metrics such as Levenshtein edit distance to measure the character-level gap between the typo and the candidate.
- Query Context: Smoothed bigram language models that assess whether the suggested words logically fit together within a phrase.
- Mailbox Content: Features that check if the candidate appears in high-signal areas like subject lines, contact names, or specific keyphrases in the email body.
- Search Context: A temporal layer that prioritizes "recent" emails and contacts. This recognizes the behavioral trend that users are more likely to search for entities they have interacted with recently.
While the features themselves are generic, the data they process is unique to the user, allowing a single global model to be trained once and deployed to provide personalized results for all users.
3. Experimental Evaluation
The researchers evaluated SpEQ using two public email corpora to ensure reproducibility:
- PALIN: Approximately 15,000 emails from former Alaska Governor Sarah Palin.
- ENRON: A subset of 2,100 emails from a specific Enron employee's "All Documents" folder.
- Query Set: A test set of 517 misspelled queries was compiled with the help of volunteers based on the content of these datasets.
4. Key Results and Insights
SpEQ significantly outperformed both a traditional source-channel ranking baseline and the built-in spelling features of a major commercial email service.
- Precision at 1 (P@1): The system achieved 89.34% accuracy on the PALIN dataset and 97.17% on the ENRON dataset.
- Comparative Improvement: This represents at least a 6.4% improvement over existing baselines.
- Ablation Studies: Feature analysis confirmed that mailbox-specific content features (e.g., matching against recent contacts or subjects) were the most critical contributors to the model's high precision.
5. Discussion and Limitations
The study highlights that in email search, the "ground truth" for spelling is the user's own mailbox rather than a standard dictionary. Furthermore, context is dynamic; the correct spelling of a query may change depending on the folder being viewed or the recency of a conversation.
However, some limitations remain. The evaluation was conducted on relatively small, specific corpora; broader testing across diverse user types (corporate vs. casual) would further validate robustness. Additionally, while the system is designed to be efficient, the paper does not provide specific millisecond-latency data, which is vital for real-time "search-as-you-type" applications. Future work may also address the "cold start" problem for new accounts with minimal email history.
6. Conclusion
SpEQ demonstrates that personalized spelling correction is not only possible but superior to global models in the context of private email search. By treating the mailbox as the primary dictionary and incorporating temporal and structural signals, SpEQ provides a highly accurate, privacy-preserving solution to the problem of misspelled queries.
Summary updated