Managing Gigabytes

Compressing and Indexing Documents and Images, Second Edition


  • Ian Witten, University of Waikato, Hamilton, New Zealand.
  • Alistair Moffat, University of Melbourne, Australia
  • Timothy Bell, University of Canterbury, U.K.

In this fully updated second edition of the highly acclaimed Managing Gigabytes, authors Witten, Moffat, and Bell continue to provide unparalleled coverage of state-of-the-art techniques for compressing and indexing data. Whatever your field, if you work with large quantities of information, this book is essential reading--an authoritative theoretical resource and a practical guide to meeting the toughest storage and access challenges. It covers the latest developments in compression and indexing and their application on the Web and in digital libraries. It also details dozens of powerful techniques supported by mg, the authors' own system for compressing, storing, and retrieving text, images, and textual images. mg's source code is freely available on the Web.

View full description


Book information

  • Published: May 1999
  • ISBN: 978-1-55860-570-1


"This book is the Bible for anyone who needs to manage large data collections. It's required reading for our search gurus at Infoseek. The authors have done an outstanding job of incorporating and describing the most significant new research in information retrieval over the past five years into this second edition."
—Steve Kirsch, Cofounder, Infoseek Corporation

"The new edition of Witten, Moffat, and Bell not only has newer and better text search algorithms but much material on image analysis and joint image/text processing. If you care about search engines, you need this book: it is the only one with full details of how they work. The book is both detailed and enjoyable; the authors have combined elegant writing with top-grade programming."
—Michael Lesk, National Science Foundation
"The coverage of compression, file organizations, and indexing techniques for full text and document management systems is unsurpassed. Students, researchers, and practitioners will all benefit from reading this book."
—Bruce Croft, Director, Center for Intelligent Information Retrieval at the University of Massachusetts

Table of Contents

PREFACE1. OVERVIEW 1.1 Document databases 1.2 Compression 1.3 Indexes 1.4 Document images 1.5 The MG system 1.6 Further reading 2. TEXT COMPRESSION 2.1 Models 2.2 Adaptive models 2.3 Huffman Coding 2.4 Arithmetic coding 2.5 Symbolwise models 2.6 Dictionary models 2.7 Synchronization 2.8 Performance comparisons 2.9 Further reading 3. INDEXING 3.1 Sample document collections 3.2 Inverted file indexing 3.3 Inverted file compression 3.4 Performance of index compression methods 3.5 Signature files and bitmaps 3.6 Comparison of indexing methods 3.7 Case folding, stemming, and stop words 3.8 Further reading 4. QUERYING 4.1 Accessing the lexicon 4.2 Partially specified query terms 4.3 Boolean query processing 4.4 Ranking and information retrieval 4.5 Evaluating retrieval effectiveness 4.6 Implementation of the cosine measure 4.7 Interactive retrieval 4.8 Distributed retrieval 4.9 Further reading 5. INDEX CONSTRUCTION 5.1 Memory­based inversion 5.2 Sort­based inversion 5.3 Exploiting index compression 5.4 Compressed in­memory inversion 5.5 Comparison of inversion methods 5.6 Constructing signature files and bitmaps 5.7 Dynamic collections 5.8 Further reading6. IMAGE COMPRESSION 6.1 Types of image 6.2 The CCITT fax standard for bilevel images 6.3 Context­based compression of bi-level images 6.4 JBIG: A standard for bilevel images 6.5 Lossless compression of continuous­tone images 6.6 JPEG: A standard for continuous­tone images 6.7 Progressive transmission of images 6.8 Summary of image compression techniques 6.9 Further reading 7. TEXTUAL IMAGES 7.1 The idea of textual image compression 7.2 Lossy and lossless compression 7.3 Extracting marks 7.4 Template matching 7.5 From marks to symbols 7.6 Coding the components of a textual image 7.7 Performance: lossy and lossless modes 7.8 System considerations 7.9 JBIG2: A standard for textual image compression 7.10 Further reading 8. MIXED TEXT AND IMAGES 8.1 Orientation 8.2 Segmentation 8.3 Classification 8.4 Further reading 9. IMPLEMENTATION 9.1 Text compression 9.2 Text compression performance 9.3 Images and textual images 9.4 Index construction 9.5 Index compression 9.6 Query processing 9.7 Further reading 10. THE INFORMATION EXPLOSION 10.1 Two millennia of information 10.2 The Internet: a global information resource 10.3 The paper problem 10.4 Coping with the information explosion 10.5 Digital libraries 10.6 Managing gigabytes better 10.7 Small is beautiful 10.8 Personal information support for life 10.9 Further reading A. GUIDE TO THE MG SYSTEM A.1 Installing the MG system A.2 A sample storage and retrieval session A.3 Database creation collection A.5 Nontextual files A.6 Image compression programs B. GUIDE TO THE NZDL B.1 What's in the NZDL? B.2 How the NZDL works B.3 Implications B.4 Further reading REFERENCES INDEX