Browsing by Author "Nevill, Craig G."

Now showing 1 - 2 of 2
  • Thumbnail Image
    ItemOpen Access
    INDEXING AND COMPRESSING FULL-TEXT DATABASES FOR CD-ROM
    (1990-11-01) Witten, Ian H.; Bell, Timothy C.; Nevill, Craig G.
    CD-ROM is an attractive delivery vehicle for full-text databases. Because of large storage capacity and low access speed, carefully-designed indexing structures--including a concordance--are necessary to enable the text to be retrieved efficiently. However, the indexes are sufficiently large that they tax the ability of main store to hold them when processing queries. The use of compression techniques can substantially increase the volume of text that a disk can accommodate, and substantially decrease the amount of primary storage needed to hold the indexes. This paper describes a suitable indexing mechanism, and its compression potential using modern compression methods. It is possible to double the amount of text that can be stored on a CD-ROM disk \fIand\fR include a full concordance and indexes as well. A single disk can accommodate around 180 million words of text--equivalent to a library of 1000-1500 books--and provide rapid response to a variety of queries involving multiple search terms and word fragments.
  • Thumbnail Image
    ItemOpen Access
    MODELS FOR COMPRESSION IN FULL-TEXT RETRIEVAL SYSTEMS
    (1990-08-01) Witten, Ian H.; Nevill, Craig G.; Bell, Timothy C.
    Text compression systems operate in a stream-oriented fashion which is inappropriate for databases that need to be accessed through a variety of retrieval mechanisms. This paper develops models for full-text retrieval systems which (a) compress the main text so that it can be randomly accessed via synchronization points; (b) store the text's lexicon in a compressed form that can be efficiently searched for concordancing and decoding purposes; (c) include a lexicon of word fragments that can be used to implement retrieval based on partial word matches; and (d) store the text's concordance in highly compressed form. All compression is based on the method of arithmetic coding, in conjunction with static models, derived from the text itself. This contrasts with contemporary stream-oriented compression techniques that use adaptive models, and with database compression techniques that use ad hoc codes rather than principled models. A number of design trade-offs are identified and investigated on a 2.7 million word sample of English text. The paper is intended to assist designers of full-text retrieval systems by defining, documenting and evaluating pertinent design decisions.