Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10355300 | Information Processing & Management | 2005 | 21 Pages |
Abstract
Signature files and inverted files are well-known index structures. In this paper we undertake a direct comparison of the two for searching for partially-specified queries in a large lexicon stored in main memory. Using n-grams to index lexicon terms, a bit-sliced signature file can be compressed to a smaller size than an inverted file if each n-gram sets only one bit in the term signature. With a signature width less than half the number of unique n-grams in the lexicon, the signature file method is about as fast as the inverted file method, and significantly smaller. Greater flexibility in memory usage and faster index generation time make signature files appropriate for searching large lexicons or other collections in an environment where memory is at a premium.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science Applications
Authors
Ben Carterette, Fazli Can,