# A Fast Randomized Algorithm for Massive Text Normalization

arXiv: https://arxiv.org/abs/2110.03024 · HTML: https://mlsanity.com/paper/2110.03024/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 54 references that are in the map.
- First posted on arXiv 6 Oct 2021.

## Builds on (most cited first, 14 of 14)

- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Advances in Pre-Training Distributed Word Representations](https://mlsanity.com/paper/1712.09405/) (2017)
- [Semantic Product Search](https://mlsanity.com/paper/1907.00937/) (2019)
- [Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1410.5410/) (2014)
- [Efficient Twitter Sentiment Classification using Subjective Distant Supervision](https://mlsanity.com/paper/1701.03051/) (2017)
- [Optimal Densification for Fast and Accurate Minwise Hashing](https://mlsanity.com/paper/1703.04664/) (2017)
- [Improved Densification of One Permutation Hashing](https://mlsanity.com/paper/1406.4784/) (2014)
- [Training and Prediction Data Discrepancies: Challenges of Text Classification with Noisy, Historical Data](https://mlsanity.com/paper/1809.04019/) (2018)
- [Towards robust word embeddings for noisy texts](https://mlsanity.com/paper/1911.10876/) (2019)
- [Unique Entity Estimation with Application to the Syrian Conflict](https://mlsanity.com/paper/1710.02690/) (2017)
- [Hitachi at SemEval-2020 Task 12: Offensive Language Identification with Noisy Labels using Statistical Sampling and Post-Processing](https://mlsanity.com/paper/2005.00295/) (2020)
- [Robust Embeddings Via Distributions](https://mlsanity.com/paper/2104.08420/) (2021)

## Abstract (arXiv)

Many popular machine learning techniques in natural language processing and data mining rely heavily on high-quality text sources. However real-world text datasets contain a significant amount of spelling errors and improperly punctuated variants where the performance of these models would quickly deteriorate. Moreover, real-world, web-scale datasets contain hundreds of millions or even billions of lines of text, where the existing text cleaning tools are prohibitively expensive to execute over and may require an overhead to learn the corrections. In this paper, we present FLAN, a scalable randomized algorithm to clean and canonicalize massive text data. Our algorithm relies on the Jaccard similarity between words to suggest correction results. We efficiently handle the pairwise word-to-word comparisons via Locality Sensitive Hashing (LSH). We also propose a novel stabilization process to address the issue of hash collisions between dissimilar words, which is a consequence of the randomized nature of LSH and is exacerbated by the massive scale of real-world datasets. Compared with existing approaches, our method is more efficient, both asymptotically and in empirical evaluations, and does not rely on additional features, such as lexical/phonetic similarity or word embedding features. In addition, FLAN does not require any annotated data or supervised learning. We further theoretically show the robustness of our algorithm with upper bounds on the false positive and false negative rates of corrections. Our experimental results on real-world datasets demonstrate the efficiency and efficacy of FLAN.