File Compression for Simple Associative Search.
Abstract
Large data files can often be compressed greatly for retrieval purposes if the family of questions to be asked of the file can be circumscribed in advance. The author investigates in the paper methods for compressing a file D, which consists of a single long list of words, with respect to simple associative search (exact match): is any given word q contained in D. A tight lower bound on the size of the compressed file is derived. Twelve engineering solutions to this problem are evaluated and compared, mainly on the basis of how closely they approach this bound. Other comparison criteria include the amount of time and additional hardware required both for searching and for updating the compressed life. (Modified author abstract)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1973
- Accession Number
- AD0771314
Entities
People
- William H. Kautz
Organizations
- SRI International