Table of Contents

Preface

Chapter 1: Overview

• Document databases.
• Compression.
• Indexes.
• Document images.
• The mg system.
• Further reading.

Chapter 2: Text Compression

• Models.
• Adaptive models.
• Huffman Coding: Canonical Huffman codes, Computing Huffman code lengths, Summary.
• Arithmetic coding: How arithmetic coding works, Implementing arithmetic coding, Maintaining cumulative counts.
• Symbolwise models: Prediction by Partial Matching, Block-sorting compression, Dynamic Markov Compression, Word-based compression.
• Dictionary models: The LZ77 family of adaptive dictionary coders, The GZip variant of LZ77, The LZ78 family of adaptive dictionary coders, The LZW variant of LZ78.
• Synchronization: Creating synchronization points, Self-synchronizing codes.
• Performance comparisons: Compression performance, Compression speed, Other performance considerations.
• Further reading.

Chapter 3: Indexing

• Sample document collections.
• Inverted file indexing.
• Inverted file compression: Nonparameterized models, Global Bernoulli model, Global observed frequency model, Local Bernoulli model, Skewed Bernoulli model, Local hyperbolic model, Local observed frequency model, Context-sensitive compression.
• Performance of index compression methods.
• Signature files and bitmaps: Signature files, Bitsliced signature files, Analysis of signature files, Bitmaps, Compression of signature files and bitmaps.
• Comparison of indexing methods.
• Case folding, stemming, and stop words: Case folding, Stemming, Effect on index size, Stop words.
• Further reading.

Chapter 4: Querying

• Accessing the lexicon: Access structures, Front coding, Minimal perfect hashing, Design of a minimal perfect hash function, Disk-based lexicon storage.
• Partially specified query terms: Brute force string matching, Indexing using n-grams, Rotated lexicons.
• Boolean query processingConjunctive queries, Term processing order, Random access and fast lookup, Blocked inverted files, Nonconjunctive queries.
• Ranking and information retrieval: Coordinate matching, Inner product similarity, Vector space models.
• Evaluating retrieval effectiveness: Recall and precision, Recall-precision curves, The TREC project, World Wide Web searching, Other effectiveness measures.
• Implementation of the cosine measure: Within-document frequencies, Calculating the cosine value, Memory for document weights, Memory for accumulators, Fast query processing, Frequency-sorted indexes, Sorting.
• Interactive retrieval: Relevance feedback, Probabilistic models.
• Distributed retrieval.
• Further reading.

Chapter 5: Index Construction

• Memory-based inversion.
• Sort-based inversion.
• Exploiting index compression: Compressing the temporary files, Multiway merging, In-place multiway merging.
• Compressed in-memory inversion: Large memory inversion, Lexicon-based partitioning, Text-based partitioning.
• Comparison of inversion methods.
• Constructing signature files and bitmaps.
• Dynamic collections: Expanding the text, Expanding the index.
• Further reading.

Chapter 6: Image Compresion

• Types of image.
• The CCITT fax standard for bilevel images.
• Context-based compression of bilevel images: Context models, Two-level context models, ``Clairvoyant'' compression.
• JBIG: A standard for bilevel images: Resolution reduction, Templates and adaptive templates, Coding and probability estimation.
• Lossless compression of continuous-tone images: The GIF and PNG lossless image formats, FELICS: Fast, efficient, lossless image compression system, CALIC: context-based adaptive lossless image codec, JPEG-LS: a new standard for lossless image compression.
• JPEG: A standard for continuous-tone images.
• Progressive transmission of images: Pyramid coding, Compression for pyramid coding, Median aggregation, Error modeling.
• Summary of image compression techniques.
• Further reading.

Chapter 7: Textual Images

• The idea of textual image compression.
• Lossy and lossless compression.
• Extracting marks: Tracing the boundary of a mark, Removing the mark from the image, Sorting marks into natural reading order.
• Template matching: Global template-matching, Local template-matching, Compression-based template-matching, Screening library templates, Evaluation of template-matching methods.
• From marks to symbols: Library construction, Symbols and their offsets.
• Coding the components of a textual image: Library, Symbol numbers, Symbol offsets, Original image.
• Performance: lossy and lossless modes.
• System considerations.
• JBIG2: A standard for textual image compression.
• Further reading.

Chapter 8: Mixed Text and Images

• Orientation: Detecting straight lines using the Hough transform, Left-margin search, The projection profile, From slope histogram to docstrum.
• Segmentation: Bottom-up segmentation methods, Top-down and combined segmentation methods, Mark-based segmentation, Segmenting short text strings, Segmentation using a document grammar.
• Classification.
• Further reading.

Chapter 9: Implementation

• Text compression: Choice of compression model, Choice of coder, Limitations on Huffman codes, Length-limited coding.
• Text compression performance: Compression effectiveness, Decompression speed, Decompression memory, Dynamic collections.
• Images and textual images: Compression of bilevel images, Compression of grayscale images, Compression of textual images.
• Index construction.
• Index compression.
• Query processing: Boolean queries, Ranked queries.
• Further reading.

Chapter 10: The Information Explosion

• Two millennia of information.
• The Internet: a global information resource.
• The paper problem.
• Coping with the information explosion: Web search engines, Agent-based information retrieval, Data mining.
• Digital libraries.
• Managing gigabytes better.
• Small is beautiful.
• Personal information support for life.
• Further reading.

Appendix A: Guide to the mg System

• Installing the mg system.
• A sample storage and retrieval session.
• Database creation.
• Querying an indexed document collection.
• Nontextual files.
• Image compression programs.

Appendix B: Guide to the NZDL

• What's in the NZDL?: Computer Science Technical Reports, Other collections, Collection development, Audio and music, Melody index.
• How the NZDL works: The raw material, Searching and indexing.
• Implications.
• Further reading.