INTRODUCTION TO MODERNINFORMATION RETRIEVAL i

SCIEN CESER IESIntroduction
to Modem
Information Retrieval

McGraw-Hill Computer Science Series
Ahuja: D esign and A nalysis o f Computer Com m unication N etw orks
Allen: A natom y o f LISP
Barbacci and Siewiorek: T he D esign and A nalysis o f Instruction Set P rocessors
Bell and Newell: Computer Structures: Readings and E xam ples
Donovan: S ystem s ProgrammingGear: C om puter Organization and Programming
Givone: Introduction to Sw itching Circuit Theory
Goodman and Hedetniemi: Introduction to the D esign and A nalysis o f Algorithm s
Ham acher, Vranesic, and Zaky: Computer Organization
Hamming: Introduction to A pplied Num erical A nalysis
Hayes: C om puter A rchitecture and Organization
Hellerman: Digital Computer S ystem Principles
Hellerman and Conroy: Com puter System Performance
Katzan: Microprogramming Primer
Keller: A First C ourse in C om puter Programming U sin g P A SC A L
Liu: E lem ents o f D iscrete M athem atics
Liu: Introduction to Combinatorial M athem atics
MacEwen: Introduction to Com puter System s: U sin g the PDP-11 and Pascal
M adnick and Donovan: Operating S ystem s
Manna: M athem atical T heory o f Computation
Newman and Sproull: Principles o f Interactive C om puter Graphics
Nilsson: Problem -Solving M ethods in Artificial Intelligence
Payne: Introduction to Sim ulation: Programming T echniques and M ethods o f A nalysis
Rice: Matrix Com putations and M athem atical Software
Salton and McGill: Introduction to M odern Information Retrieval
Shooman: Software Engineering: D esign , R eliability, and M anagement
Siewiorek, Bell, and Newell: Com puter Structures: Principles and E xam ples
Stone: Introduction to Com puter Organization and D ata Structures
Stone and Siewiorek: Introduction to Computer Organization and D ata Structures:
PDP-11 Edition
Tonge and Feldman: Computing: An Introduction to Procedures and Procedure-Followers
Tremblay and Bunt: A n Introduction to Computer Science: A n Algorithm ic Approach
Tremblay and Bunt: An Introduction to Computer Science: A n Algorithm ic Approach,
Short Edition
Tremblay and Manohar: D iscrete M athem atical Structures with A pplications to C om ­puter S cien ce.
Tremblay and Sorenson: A n Introduction to D ata Structures with A pplications
Tucker: Programming Languages
W iederhold: D atabase D esign

McGraw-Hill Advanced Computer Science Series
Davis and Lenat: K n ow ledge-B ased S ystem s in Artificial Intelligence
Kogge: T he Architecture o f Pipelined Computers
Lindsay, Buchanan, Feigenbaum , and Lederberg: A pplications o f Artificial Intelligence
for Organic Chemistry: T he Dendral Project
Nilsson: Problem -Solving M ethods in Artificial Intelligence
W ulf, Levin, and Harbison: Hydra/C.m mp: An Experim ental Computer S ystem

Introduction
to Modem
Information Retrieval
Gerard Salton
Professor of Computer Science
Cornell University

Michael J. McGill
Associate Professor of Information Studies
Syracuse University

McGraw-Hill Book Company
New York St. Louis San Francisco Auckland Bogota Hamburg
Johannesburg London Madrid Mexico Montreal New Delhi
Panama Paris Sao Paulo Singapore Sydney Tokyo Toronto

This book was set in Times Roman by Progressive Typographers.
The editors were Charles E. Stewart and James E. Vastyan;
the production supervisor was John Mancia.
The drawings were done by VIP Graphics.
R. R. Donnelley & Sons Company was printer and binder.

INTRODUCTION TO MODERN INFORMATION RETRIEVAL
Copyright © 1983 by McGraw-Hill, Inc. All rights reserved. Printed in the United Statesof America. Except as permitted under the United States Copyright Act of 1976, no partof this publication may be reproduced or distributed in any form or by any means, orstored in a data base or retrieval system, without the prior written permission of the pub­lisher.
1 2 3 4 5 6 7 8 9 0 DODO 8 9 8 7 6 5 4 3 2ISBN
Library of Congress Cataloging in Publication Data
Salton, Gerard.
Introduction to modern information retrieval.
(McGraw-Hill computer science series)
Includes indexes.
1. Information storage and retrieval systems.
I. McGill, Michael J. II. Title. III. Series.
Z699.S313
025'.04
81-20843
ISBN 0-07-054484-0
AACR2

Contents

Preface
CHAPTER 1

CHAPTER 2

xi

Information Retrieval: An Introduction

1

0 P review
1 O verview
2 Changing T echnology
3 Information System T ypes
A Information Retrieval Systems
B Data Base Management Systems
C Management Information Systems
D Decision Support Systems
E Question-Answering Systems
4 Functional Approach to Information Retrieval
5 Sim ple F ile Structures
A Linear Lists
B Ordered Sequential Files*C Indexed Files
6 Summary

1
11
5
7
7
8
8
9
9
10
12
12
13
16
|21

Systems Based on Inverted Files>24i.

0 Preview
1 General Considerations

j.24
j24
i v

vl

CHAPTER 3

CONTENTS

A Boolean Expressions
B Order of Operations
2 A djacency and Term Frequency Features
A Adjacency Operations
B Frequency Information
3 C om m ercial Inverted File S ystem s
A The DIALOG System*B The STAIRS System
C The Bibliographic Retrieval Services (BRS) System
D The MEDLARS System .
E The ORBIT System
F The Information BankG The LEXIS System
4 E nhancem ents o f B asic R etrieval Strategy

25
26
28
28
30
30
30
34
41
42
45
45
46
46

Text Analysis and Automatic Indexing

52

0 P review
1 Indexing Environm ent
2 Manual and A utom atic Indexing
3 A utom atic Term E xtraction and W eighting
A General Considerations*B The Inverse Document Frequency Weight**C The Signal-Noise Ratio*D The Term Discrimination Value
4 A Sim ple A utom atic Indexing P rocess
5 A utom atic Term A ssociation and U se o f C ontext
A Thesaurus Rules*B Automatic Thesaurus Construction
C Thesaurus Use
D Construction of Term Phrases
E Automatic Sentence Extraction
6 Som e T heoretical A pproaches

7 A utom atic Indexing E xperim ents

52
53
55
59
59
63
63
66
71
75
75
78
81
84
87
90
90
93
94
99

The SMART and SIRE Experimental
Retrieval Systems

118*A The Use of Linguistic Methods*B Fragment Encoding**C Probabilistic Information Retrieval

CHAPTER 4

0 P review
1 Introduction
2 The SM A R T S ystem Environm ent*A Vector Representation and Similarity Computation*B Vector Manipulation
C Vector Generation
3 SM A RT S ystem Procedures*A Automatic Indexing*B Automatic Document Classification*C Relevance Feedback Operations*D Dynamic Document Space

118
118
120
120
123
127
130
130
137
140
145

CONTENTS
4

CHAPTER 5

A utom atic E nhancem ents o f C onventional Retrieval*A Document Ranking and Term Weighting*B Retrieval through Man-Machine Dialogue andLocal Clustering

146
146

Retrieval Evaluation

157

0 P review
1 Introduction
2 E valuation o f Retrieval E ffectiven ess*C The Computation of Recall and Precision
3 M easures o f Retrieval E ffectiv en ess
A Measurement Problems*B Recall, Precision, and Fallout**C Single-Valued Measures**D Utility Measure
4 Evaluation o f S ystem C ost and E fficiency
A System Tradeoffs**B Cost Analysis
5 Summary

157
158
159
159
161
164
172
172
174
177
184
186
186
187
191

Retrieval Refinements

199

0 P review
1 Introduction*2 V ector Similarity Functions
3 Term W eighting S ystem s
A Principal Weighting Strategies*B Evaluation of Weighting Systems**C Term Weighting in Boolean Query Systems
4 File Clustering*A Main Considerations*B Classification Methods*C Cluster Search Evaluation**D Automatic Pseudoclassification
5 D ynam ic Query Adjustm ent
A General Considerations*B Feedback Theory

6 Citation P rocessing
A Basic Citation Properties*B Main Citation Usage
7 Summary

199
200
201
204
204
207
211
215
215
220
222
227
236
236
238
240
244
246
246
247
250

Natural Language Processing

257

0 P review
1 C om ponents o f Natural Language S ystem s
A Interest in Natural Language Processing

257
258
258

A System Components
B Evaluation Viewpoints and the Relevance Problem

CHAPTER 6*C Feedback Variations
D Dynamic Document SpaceCHAPTER 7

151

viii

CONTENTS
B Levels of Language Processing
C Language Understanding Systems
2 Language Processing and Inform ation Retrieval
3 Syntactic A nalysis S ystem s*A Phrase Structure Grammars*B Transformational Grammars**C Augmented Transition Network Grammars
4 Syntactic A nalysis in Information Retrieval
5 Linguistic M ethods in Q uestion A nsw ering**A Knowledge Representation

6 Summary

259
261
266
267
268
273
276
284
287
287
291
292
297

Access to Information: Hardware andSoftware Approaches

303

B Question-Answering Environment*C Linguistic Features in Question Answering

CHAPTER 8

0 P review
1 C onventional Storage D ev ic e s
A Punched Cards
B Magnetic Tape**E String Matching Using the Finite State Automaton Model**F The Boyer and Moore String Matching Method
4 Summary

303
303
304
306
307
308
309
310
312
312
314
316
317
320
322
324
326
328
329
329
333
338
339
340
345
348

Data Management Systems354

0 P review
1 T ypes o f Inform ation S ystem s
A Information Retrieval and Question Answering
B Data Management Systems. 2 The Structure o f Data B ase M anagem ent S ystem s
A Basic Concepts
B Structure of Information Items

354
355
355
357
359
359
362

C Magnetic Disks
D Random Access Storage Devices
E Data Cell
F Access to Storage
2 Hardware E nhancem ent o f Retrieval
A Microprocessors and Processing Chips
B General Characteristics of Retrieval Hardware
C Parallel Processors*D Associative Processors*E Fast Computations Using Array Processors*F Content Addressable Segment Sequential Memory (CASSM)*G Relational Associative Processors (RAP)*H Data Base Computer (DBC)
I Other Special-Purpose Devices
3 T ext A c c e ss M ethods*A Dictionary Search Methods for Static Files*B Dictionary Search Methods for Dynamic Files*C Multiple Key Dictionary Search
D Text Scanning Machines

CHAPTER 9

CONTENTS

CHAPTER 10ix*C The Relational Data Base Model*D The Hierarchical Data Base Model*E The Network Data Base Model
3 Query P rocessing*A Query Language Types*B Processing Strategies
4 D ata Quality*A Integrity and Security**B Concurrent Data Base Operations**0 Restart and Recovery Methods**D Distributed Data Bases
5 Summary

365
370
377
380
380
386
390
390
394
398
399
401

Future Directions in Information Retrieval

408

0 P review
1 Introduction
2 T echnological D evelopm ents

408
409
410
410
413
418
418
421
422
425
426
426
428
430

A Automatic Document Input
B Optical Storage
3 Inform ation T heories and M odels
A Natural Language Processing**B Fuzzy Set Theory**C Term Dependency Models*D Composite Document Representations
4 A dvanced Information S ystem s

A Mixed Information Retrieval Systems
B Personal Computing and Paperless Information Systems
5 C onclusion

IndexesName Index
Subject Index

437

Preface

An information retrieval system is an information system, that is, a systemused to store items of information that need to be processed, searched, re­trieved, and disseminated to various user populations. Information retrieval
systems thus share many of the concerns of other information systems, such asdata base management and decision support systems. In particular, it is neces­sary to choose efficient organizations for the stored records, rapid search pro­cedures capable of finding items of interest in specific cases, and effective
methods for disseminating the retrieved data and interacting with the systemusers.
|
Information retrieval systems are normally used to handle bibliographic
records and textual data. This is in contrast to data base management and man­agement information systems that process structured data, and to question-an­
swering systems that use complex information organizations and inference pro­cedures designed to answer questions in particular subject areas. In an
extended sense, however, any information system designed to augment thestate of human knowledge and to aid human activities does utilize concepts andprocedures from information storage and retrieval.
Today, information processing activities are carried out with the assist­ance of automatic equipment. Thus, a direct link exists between information
1
xi

xii

PREFACEretrieval and computer science. On the other hand, information retrieval also
takes on aspects of behavioral science, since retrieval systems are designed toaid human activities.
Most practitioners interested in the design and operations of actual re­trieval systems are concerned only about applied computer science. However,many topics in theoretical computer science are also of direct importance toinformation retrieval, including, for example, information theory, probability
theory, computational semantics, and programming theory and algebra. Tech­niques from these disciplines may be used to build information retrieval models
and to obtain insights into various aspects of retrieval theory and practice.
Although information retrieval is mentioned in many computer sciencecurriculum proposals, retrieval courses are often replaced in practice by ma­
terial on data structures and data base systems where attractive approaches
have been developed for formalization and abstraction. The study of informa­tion retrieval is thus frequently carried out in library science, information sci­ence, and information management schools. In these environments, the mathe­
matical foundations necessary to make a substantial impact are often omitted
from retrieval system courses.
This text is aimed at increasing the understanding of modern information
retrieval by students of computer science as well as by students of information
science and management science. The book covers the basic aspects of infor­
mation retrieval theory and practice, and also relates the various techniques tothe design and evaluation of complete retrieval systems. The book is introduc­
tory in the sense that no prior knowledge of retrieval methodology is assumed;
it is modern because currently active trends and developments are examined.
The text concentrates in particular on the description of the concepts, func­
tions, and processes of interest in retrieval rather than on the detailed opera­
tions of any one existing retrieval system. In order to keep the material at an
introductory level, the more advanced mathematical aspects of retrieval theory
have been deemphasized or simplified. The text should thus be accessible tostudents with only a cursory knowledge of the operations of digital computersand only a superficial exposure to computer programming. More advanced
readers can supply the relevant mathematical background by consulting the ref­erences given.
The text begins With an introduction and a description of the main retrieval
processes incorporated into existing, operational systems based on keyword in­dexing and Boolean query formulations (Chapters 1 and 2). Chapter 3 contains
a detailed explanation of modern automatic indexing techniques with evalua­tion results and assessments of the importance and practical usefulness of thetechniques. Experimental retrieval systems, based in part on fully automatic
analysis, search, and retrieval methods, are covered in Chapter 4 with emphasison the design of the SMART and SIRE systems developed by the authors. The
main evaluation techniques used to assess the effectiveness and efficiency of
information retrieval systems are covered in Chapter 5 with emphasis on theuse of the well-known recall and precision measures. Chapter 6 deals with im­
portant techniques usable in the design of future systems, such as automaticPREFACE

xiii

classification methods, query negotiation, and reformulation processes used in
on-line environments, collection restructuring, and bibliographic citation pro­cessing. Language processing methods useful in retrieval, including current
syntactic and semantic methodologies, and artificial intelligence approaches tolanguage understanding are examined in Chapter 7. Chapter 8 introduces spe­cialized hardware useful in retrieval, such as parallel processing devices, arrayprocessors, and special back-end search devices useful for manipulating andsearching large data bases. Also covered are modern techniques used for dic­tionary searching and for automatic text scanning systems. The relationship be­
tween information retrieval and other information systems, such as data baseand decision support systems, is examined in detail in Chapter 9, and the cur­rent work in data base processing and data base management is described. Fi­
nally the expected future directions and developments in information retrieval
are covered in Chapter 10, including the importance and likely effect of per­sonal computers, word processing, advanced display systems, and paperless
information systems.
The text should be useful for computer science as well as library scienceand information science students on a junior-senior level in college or for begin­ning graduate students. The book can also serve the professional reader as an
introduction to the design and operations of information retrieval and manage­
ment information systems. A common core for computer science as well as in­formation science readers is contained in Chapters 1, 3, 4, and 10. Computerscience audiences should profit in addition from a complete treatment of Chap­ters 5, 6, and 8, since these chapters emphasize the more mathematical aspectsof the field and the connection to software and hardware implementations. Li­
brary and information science readers, on the other hand, should concentrateon Chapters 2 ,7 , and 9 in addition to the core to gain a thorough understandingof conventional retrieval and other information systems and of the language
analysis methods useful for processing natural language texts.
To simplify the reader’s task, the material has been graded for technicaldifficulty:*Sections marked with a single asterisk contain technical material that may
be difficult for some readers. Often a modest computer science background
may be useful, or an acquaintance with elementary algebra or basic probability
theory. This material is considered important, and the reader is encouraged toread the section and obtain an understanding of the content.
** Sections identified by two asterisks contain technical material at a some­what more detailed level. A particular procedure may be covered in detail; al­ternatively, a theory may be introduced requiring some technical know-how.
Readers who find this material difficult may wish to skim the section rather thandwell on the details.
Sections not marked by * or ** should be accessible to all readers without
special background.
The following sample curricula will provide complete coverage Of the prin­cipal aspects of retrieval system design and operations:

xiv

PREFACE

Computer science

Information scienceand management science

Chapter 1(Core)

What is information retrieval?
Functional view of retrieval

What is information retrieval?
Functional view of retrieval

Chapter 2(IS emphasis)

Basic set theory inherent in list
processing

Standard Boolean operations
Standard retrieval
Conventional systems

Chapter 3(Core)

Theory of automatic indexing
Term weighting and associativeindexing
Basic evaluation results

Theory of automatic indexing
Term weighting and associativeindexing
Basic evaluation results

Chapter 4(Core)The SMART system
Relevance feedback and cluster
searching
Weighted retrieval in Booleansystems (SIRE)

The SMART system
Relevance feedback and cluster
searching
Weighted retrieval in Booleansystems (SIRE)

Chapter 5(CS emphasis)

Mathematics of evaluation
Evaluation parameters andcomputational aspects

Basic definition ofrecall-precision parameters
Cost evaluation

Chapter 6(CS emphasis)

Term relevance theory
Cluster generation and search
Pseudoclassification
Document space alteration anddynamic file processing

Use of citations in information
search systems

Chapter 7(IS emphasis)

ATN grammars
Criterion tree processing
Concept representation

Language analysis
Syntax and semantics
Context-free andcontext-sensitive grammars
Concept representation in
information systems

Chapter 8(CS emphasis)

Basic hardware devices
Parallel processing techniques
Microprocessors
Dictionary search methods
String search algorithms

Basic hardware and parallel
processing techniques
Microprocessors
Text scanning machines

Chapter 9(CS and IS
emphasis)

Relationship of information
retrieval to other information
systems
Data base systems and models

Relationship of information
retrieval to other information
systems
File processing, accessing,searching
File security, data structures

Chapter 10(Core)

Future directions
Text input
Distributed architecture
New retrieval theories
Advanced information systems

Future directions
Text input
Distributed architecture
Mixed information retrieval
systems
Paperless information systems

PREFACExv

By limiting the coverage to the more basic aspects of the various topics,
the material can be assimilated in a one-semester course. A second semester
may be required if the various algorithms and techniques—for word stem gen­eration, pseudoclassification, string searching, and so on— are covered in de­tail, and if additional sources are consulted.
A number of graduate students at Cornell and Syracuse universities havemade substantial contributions to the design of the SMART and SIRE systems,
including, in particular: Robert E. Williamson, Clement T. Yu, Chung Shu
Yang, Anita Wong, Harry Wu, and Edward A. Fox at Cornell and Terry
Noreault, Jennifer Kuehn, Judy Tessier, and Matthew Koll at Syracuse. Sev­
eral readers have reviewed the manuscript and made many valuable comments
and suggestions, including, in particular: Professor Richard H. Austing of the
University of Maryland, Professor Michael D. Cooper of the University of Cal­
ifornia at Berkeley, Professor Jeffrey Katzer of Syracuse University, Dr. Mi­
chael E. Lesk of Bell Laboratories, Professor J. F. Nunamaker of the Univer­sity of Arizona, and Professor Linda C. Smith of the University of Illinois. The
authors have also profited from discussion with many colleagues and friends.
Some early material was typed by Peggy Montgomery at Syracuse. Geri Pinkham at Cornell has typed the complete manuscript over several times with un­
usual speed and competence; in the process she became familiar with the intri­cacies of an automated text editing system. Without her help the text would
have remained in manuscript form for a long time to come. Edward Fox andElena Seifrid have also helped to produce a version ready for automatic type­setting. The writers are greatly indebted to all these individuals for guidance
and assistance.
Gerard Salton
Michael J. McGill