de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Thesis

Efficient Large-Scale Clustering of Spelling Variants, with Applications to Error-Tolerant Text Search

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44223

Celikik,  Marjan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;
International Max Planck Research School, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45720

Weikum,  Gerhard
Databases and Information Systems, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44076

Bast,  Holger
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Celikik, M. (2007). Efficient Large-Scale Clustering of Spelling Variants, with Applications to Error-Tolerant Text Search. Master Thesis, Universität des Saarlandes, Saarbrücken.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0027-C33D-4
Abstract
In this thesis, the following spelling variants clustering problem is considered: Given a list of distinct words, called lexicon, compute (possibly overlapping) clusters of words which are spelling variants of each other. We are looking for algorithms that are both efficient and accurate. Accuracy is measured with respect to human judgment, e.g., a cluster is 100 accurate if it contains all true spelling variants of the unique correct word it contains and no other words, as judged by a human. We have sifted the large body of literature on approximate string searching and spelling correction problem for its applicability to our problem. We have combined various ideas from previous approaches to two new algorithms, with two distinctly different trade-offs between efficiency and accuracy. We have analyzed both algorithms and tested them experimentally on a variety of test collections, which were chosen to exhibit the whole spectrum of spelling errors as they occur in practice (human-made, OCR-induced, garbage). Our largest lexicon, containing roughly 25 million words, can be processed in half an hour on a single machine. The accuracies we obtain range from 88 - 95. We show that previous approaches, if directly applied to our problem, are either significantly slower or significantly less accurate or both. Our spelling variants clustering problem arises naturally in the context of search engine spelling correction 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 inverse to 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 have integrated our algorithms with the CompleteSearch engine, and show that this feature can be achieved without significant blowup in either index size or query processing time.