Fast Error-Tolerant Search on Very Large Texts

Given a list of distinct words, called lexicon, compute
(possibly overlapping) clusters of words which are spelling
variants of each other. This problem naturally arises in
the context of error-tolerant full-text search of the following
kind: For a given query, return not only documents matching
the query words exactly but also those matching their
spelling variants. This is the inverse of the well-known ”Did
you mean: ... ?” web search engine feature, where the error
tolerance is on the side of the query, and not on the side of
the documents.
We combine various ideas from the the large body of literature
on approximate string searching and spelling correction
problems to a new algorithm for the spelling variants
clustering problem that is both accurate and very efficient
in time and space. Our largest lexicon, containing roughly
25 million words, can be processed in about 18 minutes on
a standard PC using 10 MB of additional space. This beats
the previously best scheme by a factor of two in running time
and by a factor of more than ten in space usage. We have
integrated our algorithms into the CompleteSearch engine in
a way that achieves error-tolerant search without significant
blowup in either index size or query processing time.