FAST RETRIEVAL OF ELECTRONIC MESSAGES THAT CONTAIN MISTYPED WORDS OR SPELLING-ERRORS

This paper presents an index structure for retrieving electronic messa ges that contain mistyped words or spelling errors, Given a query stri ng (e.g., a search key), we want to find those messages that approxima tely contain the query, i.e., certain inserts, deletes and mismatches are allowed when matching the query with a word (or phrase) in the mes sages. Our approach is to store the messages sequentially in a databas e and hash their ''fingerprints'' into a number of ''fingerprint files .'' When the query is given, its fingerprints are also hashed into the files and a histogram of votes is constructed on the messages, We der ive a lower bound, based on which one can prune a large number of nonq ualifying messages (i.e., those whose votes are below the lower bound) during searching. The paper presents some experimental results, which demonstrate the effectiveness of the index structure and the lower bo und.