Chapter 8

Access to Information:
Hardware and Software
Approaches

0 PREVIEW

This chapter examines special-purpose devices and methodologies useful instoring and accessing collections of information items. A number of conven­tional storage devices such as cards, disks, and tape are introduced first. This
leads to the description of more specialized hardware systems that may be usedin obtaining rapid access to stored data, including parallel and associative pro­
cessors and special-purpose “ back-end” search processors. The chapter ends
with an examination of the main procedures available for accessing and pro­cessing data bases consisting of stored texts. The principal file access methods
are described, and various text matching procedures are covered which make itpossible rapidly to identify portions of text that match a given query statement.
Additional advanced hardware developments that may enhance the design offuture information retrieval systems are included in Chapter 10.
1 CONVENTIONAL STORAGE DEVICES

This chapter is concerned with the machines and procedures that are especiallydesigned for the processing and retrieval of bibliographic and textual informa303

CHAPTER 8

304

tion. A historical perspective is presented in the first section followed by a de­scription of specific devices for the manipulation of large data bases and theprocessing of large quantities of text.
Modern data processing activities as we know them have their origin long
ago, starting most likely with the beginnings of formal trade between individu­
als. When a person is involved in trade, an essential skill js the ability to decideon the worth of the item being traded in relation to the item being received. For
example, ancient traders were expected to know or keep track of how many
cattle were required in exchange for a husband or wife [1]. As the complexity of
trading grew, the need for record keeping and for mechanisms to track and pro­
cess information led to the invention of various systems of symbols (for exam­
ple, the Arabic numbers 1, 2, 3, . . . , 10) and of operations which could be
performed on those symbols (such as addition or comparison for equality). The
complexity and the speed of these processing operations has increased overtime to meet growing demands. Processing aids, such as the abacus, were soon
developed that furnish greater processing speed and increase human abilities tomaster complex problems.
Among the most noticeable advances in information processing were thegreatly enhanced capabilities for performing numerical computations [2]. As an
example, the analytical engine developed by Babbage in 1834 was specificallydesigned to aid the military purposes of Great Britain by calculating the trajec­
tories of cannons and other firearms [3]. The modern computing era began dur­ing the Second World War when automatic computing equipment was used in
Great Britain for the decoding of encrypted messages, and in the United States
for the calculation of ballistic firing tables. The interest in the automatic storage
and retrieval of bibliographic and textual information existed from the begin­ning because of the large available information collections, and the difficulties
of dealing with textual materials by conventional methods.
A

Punched Cards

A major innovation of concern in information retrieval occurred with the use by
Herman Hollerith of punched card techniques to process the data collected forthe 1890 census. Hollerith proposed using one or more paper cards for eachindividual responding to the census and encoding all responses by punchingholes into these cards at precise locations. He then designed mechanical de­vices to “look at” prespecified locations on the cards to determine if a hole had
been punched. The number of holes could then be automatically tabulated,
Hollerith used a linear scan of the set of cards which looked at the same loca­
tion in every record to determine whether a specific value was present. Hol­
lerith’s idea was enormously successful. In fact, punched cards have remained
an important medium for the storage of information through most of the historyof computers. Figure 8-1 shows a contemporary punched card of the Hollerith
design.
Punched cards can be “read” by commercially available readers at speedsof around 1,000 cards per minute. If a data base of a million characters werestored on cards, this data base would require about 12.5 minutes to read.

ri m in

Vh

«M

w

CM

CO

—
—

CM

CO

(N

CO

a
sc

*—
<—

CM

s

—

CM

e

—

a
s

—
«—

CM
CM

a

v

^ B
CM

s

—

CM

3
5

~ -

CO
CO

«0

^ B

cs
cs

I/O

CO

no

CO

r—
p»

09 ~

t/o

CO
CO

r*»
r—

B B
B 3

0 9 r.
09 ?

uo

CO

r—

CO

uo

tm
CO

^ B
r* .

MC
M

^ B
uo

I B

09 a

B B

09 2
09 a

^ B

09 S
09 3

F -

■ B

09 £

CO
CO

r—.

B B

09 £

I/O

CO

m

B B

09 3

I/O

n
CO

F—

■ B

09 2

r—

■ B
^ B

09 2

S
S

—
—

B B
CO
CO

CM

CO

s
s

*—
—

CM

CO

CM

CO

■ 1
1X0

s
53

»—
—

CM

m

s

»—

CM

K
JS

r —

CM

CO
CO

CM

CO

£

»—

CM

eo

s

—

CM

m
1X0
MS'

CO

f—

1/0

CM
m
CM

I B

CO

LXO

*—
•—

CO

09

09

I B

m

CO

O ) ~

H
r—

uo

CO
co

on a

eo
QO

CO
■ 1

CO

CM

e» &

eo

m

uo

B B
CO

CM

eo

! ■

3

CO

09 3

r -

I/O

CO

uo

m
CO

09 3

■ B

09 2

!**•
F»

I B

b b

CO

r—

^ B

09 £n
0 9 H,

mt

m

CO

r—

^ B

o> a

»—

M
CM

- CO

F*-

CO

Mj-

in
I/O

CO

^ B

to

—
—

CM

CO

*0

in

CO

F—
r—

eo
oo

CM

CO

09 3
09 3

CM

CO

CO
CO

CD

—

i/O
LXO

r—

5

eo

09 3

3
5

«—
—

CM

CO

I/O

CO

r*~

OO

09 3

CM

CO

I/O

CO

r—

eo

09 3

CM

CO

I/O
LXO

CO
CO

r*»

eo

m

CO

r—

co
B B
eo

CM

CO

3

—

CM

CO

■0

oo

5

«—

CM

CO

1X0

CO

r—

a
^

*
—
—

CM

CO

uo

CO

CM

CO

m

^ B
r-

s
r,

»—
—

CM

CO

mC

CM

co

B B

s

*—

CM

a

*—

^ B
CO

■»r

a

—

^ B
CM

a

—

CM

a

»—

CM

a

—

CM

s

~

CM

CO

CM

CO

B B
m

—

CM

s
*—
f° H

B 3
CM

M
CO
CO

MC

—

CM

CO

*0

a

•—

CM

CO

a

—

a

B B
uo

CO

r—

CO

r-

m

CO
CO

CO

uo
1X0

CO

I/O

CO

LTO

CO

UO
^ B

in

09 a

eo
B 1

M £

CO

■1
F»

eo

09 a
09 a

r—

eo

09 ?i

F—•

eo

09 £

09

09 *
09

CO

r—
r*»

CO
CO

i**-

CO

^ B
r—

CO

uo

S3

CM

CO

or

■ i
CO

a

—

CM

CO

^ B

in

CO

a

—

CM

—
B B

M
CM

B B
CO

or

in
in

CO

s
Z

CO

z
a

—
^

CM

CO

CM

CO

ts

—

CM

CO

2

*—

CM

CO

2
2

—
—

CM

CO

CM

CO

a

—

CM

=

~ -

CM

CO
CO

MC
M#-

s *—
«7> _
«>
—

— —

•* B B
*—
•» *—
"»

—'

— «—

^r

0 9 S3
cn S3

r—

CO

CO

eo
eo

F*~

uo

CM

09 3
09 v
09 3

CO

uo

CM

eo
eo

CO

uo

S

09 3
09 3

eo

eo
eo
eo

r«
F»

B B
ISO
CO

09 a

ro

’

0 9 35-C
1—

09 a
0 9 S3

eo
CO

09 ~

en a

f» »

uo

eo
eo

uo

CO

r*-

60

09 S
09 2

09 s?

m

CO
co

r—

eo

09 —

uo

09 f

CO

F^
l»—

co

m

eo

09 £'

uo
1X0

CO

1—

eo

CO

r—

B B =
o9 a

uo

CO

B B
p—

eo

09 a

CM

CO

Mj-

CO

F—

eo

= s
09 S g

CM

CO

■ i

uo

CO

t—

eo

09 o*

>

CM

M
CO

MT

uo

CO

T—

Q

CO

09 ■“

J

uo

CO

<*»
P -.

ee
eo

09 “

uo

eo

0 9 *° ®*

uo
1X0

eo

0 9 l"

CO

^ B
CM
CM

CO
CO

■O'

CM

CO

«•»

CM .
CM

CO
CO

CM

co

sn
I/O
uo

CO

r—
F—

eo

0> "

r—

eo
eo

0 9 «~
09 r

F»

eo

09 ■*

«o
CO

F-

CO

5to

09 a

eo

eo

0
n

B i~
09 a

CO
CD

uo

^

M S
09 3

eo

CO
CO

uo
uo

09 2
en 2

n—

^ B
CO

u
<3>
a
CO

09 2

3
S

*—

</)
0)
«
(Q
CO
JC
o

0 9 3>

B B
1X0

2

SS
3

.
*

0 9 Za

B B
r—

CO
CO

2

a

iiiiiiin

CO
CO

LfJ

£

a

■x
in

CM

MO
«o

V)
05
• ^
<D
-C
h-

Punched (H ollerith) card.

i

—
—

a
E

Figure 8-1

H

3
a

305

306

CHAPTER 8

Other storage media have been developed that prove to be more efficient,more reliable, and more cost effective than punched cards. Among these are
the magnetic tapes, disks, and drums. Random access storage devices such ascore or semiconductor memories have also been developed to provide rapid ac­cess to information. These devices are briefly introduced in the remainder ofthis section.
B

Magnetic Tape

The magnetic tape devices used with computers resemble the home tape re­corder. Information is stored along the length of the tape on a number of tracks.
The stored information can then be recovered by “replaying” the tape. Eachcharacter of information is represented by a sequence of magnetic spots stored
across the width of the tape. All the spots (bits) pertaining to a single characterare processed together when a character is added to, or removed from, thetape. The digital characters are commonly packed together along the length of
the tape at the rate of 1,600 or 6,250 characters per inch of tape. A typical mag­netic tape device is shown in Fig. 8-2.

Figure 8-2

Magnetic tape.

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

307

Since the information is stored on a magnetic tape in sequential order, it isnecessary to scan the tape from the beginning in order to find a specific unit of
information. Such a sequential search is potentially very slow. For example, if
one million characters are stored in records of 1,000 characters at a density of
1,600 characters per inch using a 3/4-inch gap between records, and if the tapereading speed is 125 inches per second, about 11 seconds are needed to read thetape. Furthermore, before any tape can be read, it is usually mounted on a tapedrive by a human operator. This operation may take a minute or more, de­pending on the circumstances. Tape storage is, however, inexpensive: a tapereel holding 180 million characters at a density of 6,250 characters per inch may
cost as little as $11.
C

Magnetic Disks

If a magnetic tape appears similar to a home recording tape, then a magnetic
disk resembles a phonograph record. Information is stored on a platter capableof retaining a magnetic image. This platter has concentric rings with informa­tion sequentially stored on any one ring (track). To find information on a single
platter, one needs to know which track to examine and where on that track theinformation is stored. Information is placed on a magnetic disk by means of aread-write head. In many disk devices one read-write head is used per disk
face; that is, if information is kept on both sides of the disk, two read-write
heads may be used. To locate a specific item of information, the read-write
head is moved to the appropriate track and the information is read as it passes
in front of the read head. An alternative to the moving read-write head is tohave a read-write head for every track of a disk. This head per track arrange­
ment eliminates mechanical movement (a slow process).
The magnetic disk is a direct access device because it is not necessary toscan past all preceding characters of information to get to a desired unit of in­formation. Rather it is possible to go directly to a desired track on a particular
disk. A track may store between 7,000 and 13,000 characters. A standard disk
arrangement consists of a group of disks arranged on a single shaft. Current
capacities of disk packs are in the range of 300 million characters of informa­tion. A typical disk pack is represented in Fig. 8-3.
Information can be read from magnetic disks at the rate of 100,000 charac­ters per second. Thus about 10 seconds is needed to read a data base of one
million characters. However, since it is not necessary to examine all records
sequentially on the disk, the time required to locate a specific item may bemuch less than is required for a tape. Disk storage is, unfortunately, much more
expensive than an equivalent quantity of tape storage. Disk packs may or may
not be removable from the disk drives. Removable packs may cost about $600.
Nonremovable packs are less expensive; when they are used, auxiliary tapes
may serve for off-line storage.
A recent innovation in disk technology is the small, soft, 5- to 8-inch,
floppy disk. A floppy disk is easily carried or mailed because it weighs only a
few ounces, and it is not harmed by a certain amount of bending or mistreat-

CHAPTER 8

308
Read-write headment. Floppy disks storing about one million characters may cost as little as $1
per disk. They can store anywhere from 1,000 to 3,000 or more characters per
track, with access speeds of about V2 second. Floppy disks are currently usedas the main bulk storage medium in many mini- and microcomputers.
D Random Access Storage Devices

Locating stored information items or transferring information from storage tothe computer processing unit tends to be comparatively slow on most computer
systems. This is true particularly when mechanical motion is involved, as ex­
emplified by the movement of a tape or the spinning of a disk. Devices that
require no mechanical movement for reading or writing tend to be faster. For
each such device, the time needed to read or write an item may be the same forall items, no matter where located in storage. For this reason, such devices are
known as random access devices.
Random access devices, such as core or metal oxide semiconductor(MOS) memories, tend to be expensive, although prices are declining rapidly.
At the present time a storage array for one million characters may cost about$6,000. Compared with disks and tapes, these devices provide only limited
storage capacities. That is, the capacity of a disk may be stated in billions ofcharacters, while the core and semiconductor memories may provide several
millions of characters only. Random access devices are useful because they arevery fast; one can find a specific item very quickly. A typical core storage de­vice is shown in Fig. 8-4. Information is stored in small rings, or cores, that aremagnetized in one direction or the other. The cores are arranged on a plane,and several core planes may be stacked one on top of the other. The access tothe information stored in a core array is accomplished by sensing the directionof the magnetism measured by the resistance to a prespecified current.
The reading rate for core storage is about five times greater than for disk
devices. To read a data base of a million characters requires 2 seconds for coredevices compared with the 10 seconds needed for disks. In many systems, the.performance of core or MOS memories is enhanced by using still faster andACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

309

more costly cache memories that speed up the transfer between core and thecentral processing units of the machines.
E Data Cell

In many applications a need exists for a mechanism that stores very large quan­tities of information in a cost-effective manner. A data cell is, in effect, a combi­
nation of magnetic tapes and small magnetic drums. As shown in Fig. 8-5, thisdevice uses cells containing large strips of magnetic tape. Each cell and each

310

CHAPTER 8

strip of tape within a cell is individually addressable. When a tape strip is se­lected for reading or writing, it is wrapped around a small rotating drum; theinformation on the tape can then be read as the drum rotates. Billions of charac­ters of information can be stored on a data cell rather inexpensively. Unfortu­
nately, the data cell exhibits relatively slow speed because of the mechanicalmotion required to (1) find the particular cell, (2) find the particular strip of tapein the cell, and (3) load the tape strip on the drum.
As one would expect, the mechanical motion involved in the operation of
the data cell makes this a relatively slow device. However, once a particulartape strip has been located and loaded, the device is capable of operating at
speeds corresponding to the drum rotation time. Thus a one million character
data base will require 27.5 seconds to read if the tape strip is to be located,loaded, and read.
F Access to Storage

While storage devices are often capable of storing large quantities of informa­tion, any manipulation of the stored information will traditionally occur within
the central processing unit of the computer. Hence a communications pathmust be provided between each storage device and the central processing unitof the computer system. Most central processing units have a much greater
speed than the storage devices to which they are attached. It is therefore neces­sary to speed up the information transfer by developing holding areas (buffers)
from which the information can be read more rapidly than from the storage de­vices themselves and by establishing intermediate processing devices (chan­nels) which can open and close appropriate paths, translate the information if
necessary, ensure that information is channeled to the proper location, and no­tify the central processing unit that a particular transfer process is complete.
Figure 8-6 shows the communication processes in a computer systemequipped with a variety of communications devices. The multiplexor channelinterleaves information from a number of slower devices such as card readersand punches. That is, it takes advantage of the inherent slowness of the devices
by selecting messages from a variety of active devices for transmission to thecentral processor. If a storage device is relatively fast, it is more efficient toselect and transmit all the messages from that one device before working on theinformation from some other device. A selector or burst channel is therefore
used with the faster storage devices. The tape and disk control units are used toturn the individual devices on or off and to process the information being trans­
formed.
In many situations a specific item of information will be needed from a database. More often than not the process required to access this item will interrupt
whatever else the computer may be doing at that time. Processing resumes
when the item is located and transferred to the central processing unit. If theoperations are reasonably efficient and the required data bases are small, such a
processing mode may prove acceptable. For instance, many microcomputer

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

Card
readerPrinter

311

Card
punch

Figure 8-6 Typical computer system with input-output and storage.

systems use tape cassettes for storage; information can be transferred from thecassettes at the rate of 30 characters per second. Accessing a data base of 1,250
characters (about 250 English words or 1 printed page of text) will require 41.66
seconds. Such a time frame may be acceptable to the computer hobbyist, but it
may prove unacceptable to a scientist. In many practical situations, stored databases of a million characters are common. The accessing process describedearlier could then stretch to many hours.
The use of buffers and channels will, of course, speed up the process.
However, even when additional facilities are provided for increased accessspeed, the program design and the form used to store the data often determine
the speed of the information system. In particular, even if the computer systemwere capable of performing computations in a few billionths of a second, thetrue processing time would be much slower if the machine were forced to wait
for periodic input from the data base.
A second significant feature of most computer systems is the necessity ofknowing the actual storage location of a given information item before that item
can be retrieved. That is, in order to find information records on a particular
topic the location of the corresponding information records must be known, or
else the location must be deducible from available data. If the location informa­tion is not immediately available, auxiliary index files, such as the inverted files,
are used. It would be easier and less expensive if a system were able directly tofind the needed records without concern for location. Presumably there would
then be no need for inverted files or other indexes to locate the information.
This possibility is discussed below under Associative Processors.

312

CHAPTER 8

2

HARDWARE ENHANCEMENT OF RETRIEVALA

Microprocessors and Processing Chips

For many years attempts have been made to design the ultimate information
retrieval aid. Such a device may be expected to furnish direct answers to in­coming user queries, formulate educated guesses when questions cannot be an­swered unequivocally, maintain and update personal files and appointment
schedules, and perform computations on stored data as well as translations andother transformations on natural language text. The device itself is often pic­
tured as being pocket-sized, requiring little energy to operate, and capable ofprocessing unlimited quantities of information of many kinds.
The basic idea of such a “memory extender” (Memex) is now over three
decades old, and information professionals have been striving to design thattype of retrieval engine for a long time [4,5]. In its full scope, the memory ex­tender remains outside the realm of practical possibilities for the immediate fu­ture. The enormous technological strides which have been made during the last
decade at least in the hardware area may, however, lead one to conclude thatthe time when the full Memex can actually be constructed is fast approaching.
Without a doubt the most significant trend over the past few years has been
the impressive decrease in both the size and the cost of existing electronic hard­ware devices together with a simultaneous increase in processing capability.
Complete microprocessors are currently implemented on small silicon plates,or chips, each chip including tens of thousands of active processing elements(transistors) on a plate measuring substantially less than 1 inch square. Micro­
processors are now so inexpensive to manufacture that they are incorporated
into many devices intended for home use: they have been used in particular tocontrol automobile systems, microwave ovens, and video tape equipment, andthey provide the basic processing capability in many toys and games sold tochildren and adults.
A microprocessor implementation takes many different forms. In its sim­plest form, only the chip itself is provided, which includes storage space to save
short programs and some data, as well as an arithmetic unit and a sequencecontrol unit to handle the program decoding. If a keyboard is added for manual
input and a digital readout register, one obtains a programmable device. Hand­
held models capable of text and numeric processing that will fit into one’s
pocket can be acquired for a few hundred dollars at the present time.
When substantially more internal storage capacity is furnished, typicallyfor 32,000 characters of data, and one or two soft (floppy) disks are added forexternal storage together with keyboard input and cathode ray tube display, thecost of the system jumps to $2,000 to $5,000. Such a system is then usable fortext and program editing, messaging, and many tasks needed in a question-an­
swering situation. For full information retrieval usage, an output printer be­comes mandatory, as well as a large (hard) disk for bulk storage of several mil­lion characters of text. The latter alone may add about $5,000 to the systemcost, so that a full information retrieval configuration may cost between $10,000

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

313

and $15,000 at current prices [6-9]. The microprocessor characteristics are
summarized for three typical systems in Table 8-1.
In principle, theoretical limits exist for some technological advances.
However, these limitations are not expected to affect the continued gains in theperformance/cost ratio of existing electronic devices for many decades. Fur­thermore, the conditions under which microcomputer components are cur­rently being developed lead to predictions for increasing parallelism in the pro­
cess Organization and to the existence.of “overkill” capacity in the equipment.
More specifically, since the individual integrated circuits incorporated in acomputing device are expensive to generate initially because of the human skill
needed in the design effort but, once designed, are inexpensive to produce inlarge quantities, it may be economically advantageous to produce componentsthat are rather more sophisticated than may be required for a particular applica­tion. The resulting electronic components may then be sufficiently versatile tobe used in many different capacities.
Such a deliberate overdesign implies that each chip might be used to carryout input/output manipulations, file management, memory management, inter­rupt processing, and other information transfer and processing operations. If
each function is assigned to a separate hardware component, a parallel pro­cessing capability of the kind mentioned later in this chapter results, where sev­
eral kinds of arithmetic operations are overlapped with data fetch andinput/output operations. In an information system environment, separate pro­
cessors could then be assigned to distinct system operations, and the functionsof each processor might be optimized within the context of the total system de­sign [10].
One problem to be faced when new machine architectures are introducedis the need to convert existing applications programs to the new system en­
vironment. The conversion problem becomes particularly onerous when largeTable 8-1

Microprocessor Configurations
Configuration

Handheld calculator
Digital readout
Input keyboard
Several dozen storage registers
Arithmetic unit
Automatic sequence control
Minimal processor
16- to 32-bit address
32,000 characters of data storage
2 to 5 microseconds add time
Floppy disks for storage
Cathode ray tube display
Full microprocessor configuration
Printer added to minimal processor
Hard disk for bulk storage

Typical use
Small programs andcalculations

Cost$100-$300

Word processing capability
Text editing
Program editing
Indexing
Cataloging$2,000-$5,000

Information retrieval
Inverted file processing,
Output printing$10,000-$15,000

314

CHAPTER 8

scale changes in the machine architecture are involved such as those inherentin switching from a largely sequential processing chain to a parallel processing
system. When the applications programs are originally written in some highlevel programming language, automatic translation programs may be available
to perform the required conversion. Programs written to take particular advan­
tage of the existing hardware organization, such as machine language or assem­
bly language programs, must, however, be converted by time-consuming intel­
lectual procedures.
In summary, the processing technology is becoming increasingly minia­
turized; at the same time, a trend exists toward special function architectures
where separate, sophisticated modules are devoted to specialized functions.
This may, in time, lead to a fine tuning of individual system components and to
the use of components that precisely fit a particular problem situation. The timeis rapidly aproaching when large classes of users will be able to access small,
inexpensive computers capable of satisfying sophisticated computational anddata processing requirements.
B

General Characteristics of Retrieval Hardware

It was suggested earlier that small personalized machines are becoming in­creasingly common. If these devices are to prove useful in information re­trieval, it becomes necessary to provide an interface with the large data basesthat exist in various locations. Furthermore, user terminals must be available
that are capable of displaying the retrieved information in a user-friendly man­ner.
The standard available display terminals can currently exhibit 24 lines oftext at any one time, exclusive of illustrations. Because of the low resolution of
the current displays, it is not possible to view full document pages in a conven­tional typeset format. Hence the standard display equipment is not well suitedfor the retrieval of full document texts. High-resolution terminals are coming
into use that are capable of displaying full typeset pages with illustrations,allowing 60 lines of readable text. One may expect that good-quality color
graphics can eventually be added, allowing displays of document output thatthe users will actually be happy to see displayed on a screen. At the present
time, high-resolution displays capable of controlling the display from local
memory inside the terminal are costly— somewhere between $10,000 and$20,000. These costs should decline as the equipment becomes more wide­
spread. The wide availability of small, personal machines with high-resolution
display equipment will greatly enhance the usefulness of the existing, auto­
matic retrieval services.
It has been stated that the ideal information retrieval system should havethe capacity to store between one billion and one trillion characters. The sys­
tem should also be of low cost, and it should be capable of finding the stored
data in a time period acceptable to a user waiting at a terminal for a response[ 11].

These represent stringent requirements. For example, if one assumes that

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

315

the data base consists of 1 billion characters and if a computer were to process
100,000 characters per second (about as fast as information can be read from acontemporary disk), then a user could wait for 2.7 hours for a response. Thus,
either the size of the search files must be drastically reduced or some mecha­
nism must be found for accessing these large quantities of data in a more rea­
sonable time frame.
The standard solution to this problem consists in building auxiliary index
files that identify subsections of the main files containing the information of in­terest to particular users. Alternatively, the use of special-purpose search andstorage architectures may prove useful to process large information files.
These special-purpose devices are in principle capable of processing data inde­
pendently on a stand-alone basis. More commonly, they are attached to one ormore general-purpose host machines. Each user can then access a general-pur­pose machine— possibly a personal minicomputer or a common large host ma­chine— while delegating the actual search function to the special-purpose de­vice attached to the host machine(s).
The following types of special-purpose search equipment can be distin­
guished:
1 Smart peripheral devices such as disks or drums whose normal func­tion is the storage of information. By adding special processing hardware to thedisks, information might be selected, checked, and processed right in the stor­
age device, thereby allowing a good deal of processing to take place in parallel,
and avoiding much unnecessary transfer to and from the central processing unitof the general-purpose computer(s).
2 The functions of the smart peripherals can be expanded by adding otherprocessing capabilities, thereby creating special back-end data base processors
connected to the general-purpose host machine. The general-purpose (host)machine normally controls the data base processor and handles transfers of in­formation between machines; the back-end machine is charged with specialpurpose tasks such as information search and special data base computations[ 12].

3 A number of special-purpose search computers could also be intercon­
nected by operating in a network m ode. The data stored in a given machine
might then be accessed by other machines in the network whenever this may berequired by the data base process.
In discussing each special computer configuration, it is convenient to makedistinctions based on the number of processing units available and on the typeof information search provided. In particular, a search conducted directly in a
mass storage device may be distinguished from a search conducted indirectly ina buffer or intermediate storage area [13].
When a special-purpose search computer is used, the search is initiated by
the special-purpose machine in response to a request received through a hostcomputer system as shown in Fig. 8-7. The information is examined by the spe­cial computer to determine what items should be retrieved. Records that pass
the retrievability criteria are then passed on to the host computer system. Sig-

316

CHAPTER 8

Figure 8-7

Back-end computer use for data base processing.

nificant efficiencies are achieved when the quantity of data that must be
scanned in response to each query is large, because the host computer can at­
tend to other work while the search operation takes place on the special-pur­pose machine.
If the special-purpose processor is integrated directly into a mass storage
device, the system is then capable of a direct search. That is, the central pro­cessing unit would receive a request which is then passed along to the special
mass storage device. This device will search through its data base and return tothe central processing unit only those items of information meeting the retrievability criteria.
A number of different special-purpose computer configurations are dis­cussed in the remainder of this section. In each case, the potential importanceof the device for information retrieval is briefly mentioned.
C

Parallel Processors

Multiple processor devices come in two main designs. The first is based on anumber of parallel but independent processing units. Such a configuration may
include several central processing units, each unit being capable of a wide
range of functions. For instance, two different processing units may each besearching different portions of a collection as illustrated in simplified form in
Fig. 8-8. The units may independently be able to determine the potential useful­ness of the various documents to a user query. Alternatively, each processor
might carry out different operations on the same data base in parallel, such as,
for example, word stemming, thesaurus transformation, and query-document
similarity calculations. By using several processors, the processing time for a
full data base of information items may be decreased according to the numberof processors in use [14].

Figure 8-8
cessors.

Use of separate parallel pro­

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

317

Multiple processors of this design are now in limited use in information re­trieval environments. In order to increase processing efficiency through the useof multiple, independent processors, it is necessary to identify different proce­dures that can be carried out simultaneously on different portions of the database. In information retrieval the complexity of the operations renders the
specification of parallel procedures difficult, and it is not obvious that several
processors can be kept occupied simultaneously for long periods of time.
Consider a query formulation such as (TERMt and (TERM2 r TERM3)).
Such a query may be processed in three steps as follows:
1 Use the processors in parallel to retrieve the information items asso­
ciated with TERM1; TERM2, and TERM3. This step takes advantage of theparallel capability.
2 Perform a set union operation for the sets associated with TERM2 andTERM3. This is a sequential process that might be carried out on a single pro­
cessor.
3 Perform a set intersection operation with the result of step 2 and the setof items retrieved by TERM,. This is another sequential process.
It is clear from this sequence that the advantages of the parallel processing
in step 1 may be outweighed by the extra cost and complexity due to the pres­ence of the multiplicity of processors. In general, the number of processors to
be used in a multiprocessor system should be determined by a cost-effective­
ness measure. That is, one would like to be assured that each additional pro­cessing unit will actually serve to increase the efficiency of information pro­cessing.
*D

Associative Processors

The second design for parallel processing consists in using an associative pro­
cessor containing several processing units. In this case, however, each pro­cessing unit carries out exactly the same process as every other processor ateach instant in time. The name associative processor is derived from the asso­
ciative array (matrix) storage area in which the processing of the information
occurs. Each row of this matrix is designed to accept an individual item of in­formation, and the contents of all rows are processed simultaneously. For ex­
ample, each row may be loaded with a unit of information (such as a different
query term) to be compared with a desired value. Each item will then be com­pared at the same instant with the desired value and all items meeting the de­sired search criteria will be identified simultaneously.
Figure 8-9 shows the operation of an associative processor searching forthe value BLUE among several units of text. The desired value is placed in thecomparand register in a specific set of character positions to be searched. The
locations to be searched in the array processor are identified by placing Is in
the appropriate positions of a mask register. The positions identified by Os in
the mask register (that is, positions 1 to 4 and 9 to 24 in the example of Fig. 8-9)
are ignored in the search. When a comparison is made for a particular term,

318

CHAPTER 8
Comparand register

Figure 8-9 Array processor search for term BLUE (specified as positions 5 through 8 of a
24-element row).

such as BLUE, the entire list of data elements is compared simultaneously.
Each matching data element is identified in the response register by the appear­
ance of a 1 [15].
Instead of performing parallel search operations, associative processors
could also be used to perform arbitrary parallel computations on all elements of
the associative array. Thus, in a vector oriented system such as the SMART
system, a device that could perform simultaneous calculations between a set of
document vectors and a query vector would have great advantages over a sys­
tem in which the calculations are carried out one document at a time. For ex­
ample, the calculation of the similarity between a query in the comparand regis­
ter and each document in the associative array might be performed in thefollowing way:
1 Load the document vectors into the associative store.
2 Load the query vector into the comparand register.
3 Set the mask register so that the character positions correspond to thelocations of the weights of the individual query terms.
4 Instruct the associative processor to perform a sum of product opera­
tions for the elements of the query vector with each element of all document
vectors.
The last step will simultaneously multiply each term weight of the query
vector with each term weight of corresponding terms in the document vectors.
The resulting products are then summed and placed in the response register.
The result corresponds to the numerator of the cosine similarity between thequery and each document vector stored in the associative array. Note that

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

319

three of the four steps in this process are concerned with setting up the associa­
tive processor prior to the actual vector computations.
The advantages of associative processing are numerous. Note specificallythat there is no need to be concerned with the location in storage of a desired
item until the item has met the desired search criteria. Note also that one may
conduct partial searches for terms such as BL*E, where the third character
identified by an asterisk is not specified. No preliminary processing is needed
since the data are examined by content rather than location. There is therefore
no need to prespecify the location of documents by using an index.
Unfortunately, the use of associative processing also entails many disad­vantages. A large problem is simply the necessary transfer of information into
the associative processor. This is normally carried out as a sequential process
which is thus relatively slow. Second, the location in which a given term value
appears in the associative processor must be specified precisely. Third, the costof associative processing equipment is high, and the existing associative memo­ries are small.
An example of an associative array processor is the Staran, developed by
Goodyear Aerospace. The original design was intended for the processing ofimages [16]. This design has already been shown to be useful in data base man­agement environments.
Staran is composed of 32 separate matrices (arrays), each matrix consist­ing of 256 rows and 256 columns. If one assumes that each character requires 8
columns of matrix storage, then each matrix can store a maximum of 8,192
characters, or 256 rows of 32 characters each. All the matrices are connected toa single comparand and a single mask register. Each matrix does, however,
have its own response register. An operation may be conducted on all the ma­trices simultaneously. Figure 8-10 shows the basic architecture of a system
which includes a Staran associative processor.
For information retrieval one sees immediate application of a device suchas Staran to provide a parallel search of an inverted index. This can be done byloading all the terms included in the inverted index in the associative array of

Figure 8-10

Staran organization.

CHAPTER 8320

the Staran and passing the query terms through the comparand register. Whena match is obtained between a query term and a term stored in the array, thecorresponding list of document identifiers may become immediately available.
In such an application, the tradeoff is between the high cost of associative pro­cessing compared with the cost of the contemporary software methods used toperform inverted file manipulations.
*E

Fast Computations Using Array Processors

Many computer applications areas are distinguished chiefly by the need for
substantial computational power. For example, in signal processing, large
masses of data are received as a continuous stream from external devices, suchas radar or satellite equipment, and must be processed and “cleaned up.” Insuch circumstances, the need for fast internal computation becomes over­whelming. To respond to this demand, special processors, known as “arrayprocessors” (AP), have been developed that provide very fast arithmetic oper­
ations and work in conjunction with a general-purpose computer (the host com­puter) to which they are attached. The computational APs are not to be con­fused with the associative processors used mostly for searching that were
described previously [17,18],
Array processors are normally implemented as specialized high-speed
floating-point machines (that is, they perform computations on floating-point
numbers) working in parallel with their host computer. N o character manipu­
lation or input-output facilities are normally provided. The computational
power of APs is due to two main features:
1 Parallel functional units: instead of including all arithmetic and logical
functions of the processor in a single “ arithmetic and logical unit” as is done instandard computers, the various functions of the central processing unit are
split up into separate functional units that can all operate in parallel; thus in anarray processor it is possible to perform an addition in the adder, and also amultiplication in the multiplier, and also a fetch operation to retrieve an item ofdata from memory, and also an instruction decoding operation, all these opera­
tions being carried out in parallel using separate functional units.
2 Pipelined functional units: some units of the array processor are pipe­
lined to speed up the processing of a single function, notably addition and mul­
tiplication; this means that a given operation is carried out in steps, or stages, insuch a way that a given processing unit can effectively carry out several opera­
tions at the same time, provided each operation is in a separate stage. A pipe­
lined processing unit, such as a multiplier, consisting of three stages is shown
schematically in Fig. 8-11. Three operations (multiplications) can in principle
be carried out in the multiplier at the same time: the first multiplication that wasstarted earliest is in stage 3 in the illustration of Fig. 8-11, the second multiplica­tion started one stage later is in stage 2, and the third started most recently is instage 1. After each time unit the pipelined processor advances by one stage;that is, a new operation can be started in each unit of time if the pipeline isfilled, the results of the operation being available three stages later.

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

321

Input

Stage 1

Third operation

Stage 2

Second operation

Stage 3First operation

OutputFigure 8-11

Pipelined processing unit.

Because of the limited set of functions provided, the cost of AP processing
is low (typically $40 per hour) compared with the cost of a large standard com­puter (typically $1,000 per hour).
When an array processor is coupled to a general-purpose (host) computer
as shown in Fig. 8-12, all input-output, program setup, and data base operations
are normally carried out by the host. Computational tasks can, however, beassigned to the AP after transfer by the host of relevant instructions and data
into the array processor. The AP then executes its program while the host waits
or performs other tasks unrelated to what is going on inside the AP. When the
AP finishes its task, a “device interrupt” is sent to the host; the host then reads
the results out of the AP, and processing continues.
, Whether it pays to use an AP with a host computer depends on whether thesavings obtained by executing a routine in the AP outweigh the costs of com­municating programs and data between host and AP. The following factors ap­
pear important in this connection:
1 The data manipulations should be executable as floating-point arithme­
tic rather than as address, character, or integer manipulations.

Consoledevices.

General-purpose
host computer

Input-output
channelOther input-output
devices (disks, printer)

Figure 8-12

Simplified diagram of host-AP system.

Arrayprocessor

322

CHAPTER 8

2 The application should include long computations to justify the re­quired host overhead and data transfer time.
3 The program to be executed should be small.
4 The data required by the AP should be easy to select.
Information retrieval appears, at first, to furnish a poor application for APs
because of the large data base to be processed and the many data transforma­tions as opposed to arithmetic operations to be performed. On the other hand,
it is obvious from the material in the preceding chapters that the computational
requirements are certainly not negligible in many information retrieval proces­sors. Examples are the computation of similarity coefficients between vectors,
the generation of term weighting functions such as the term discrimination andterm relevance values, the generation Of cluster centroids for clustered docu­
ment collections, and the computation of recall-precision factors.
Consider, as an example, the computation of the cosine function between
DOCi and QUERYj defined as
2 TERMik • QTERMjk
k=l

Looking only at the numerator of the cosine function, the following operations
appear to be executable in parallel on an array processor of the type illustrated
in Fig. 8-13:
1 The multiplication of the vector element TERMik with the element
QTERMjk
2 The addition of the previous factor TERMi>k_i • QTERMjjk_j to thesum of the previous k - 2 products
3 The memory fetching operation required to extract terms TERMijk+1
and QTERMj>k+1 from memory
In these circumstances, the parallelism of the AP unit appears to be immedi­
ately useful. Detailed analyses of the use of parallel computing facilities in in­formation retrieval remain to be carried out [19].
*F

Content Addressable Segment Sequential Memory (CASSM)

The content addressable segment sequential memory (CASSM) was designed
and built at the University of Florida as a general-purpose device, of benefit to
all nonnumeric applications including information retrieval. The basic CASSM
design is presented in Fig. 8-14. The CASSM design provides a number of dis­tinct cells, each cell consisting of a storage unit and a separate processing unit.
During a search operation, the various cells operate in parallel, and all the pre-

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

323

Figure 8-13 Typical floa ting -point array processor (constants, data, and instructions are
kept in separate memories; m ultiplier and adder are pipelined; integer arithm etic, instruction
decoder, adder, and m ultiplier are separate functional units).

Each cell controlsa small portion of
the data base store

Figure 8-14

CASSM system organization. (Adapted from reference 13.)

324

CHAPTER 8

liminary processing needed to choose the items to be retrieved is done in the
CASSM device rather than the host machine. The actual implementation of the
CASSM prototype was carried out on a special disk modified to include reading
and writing units for each track of the disk [20].
An initial assumption of the CASSM design is that the entire data base willreside within the CASSM device used for data base storage. Thus, as the size ofthe data base increases, the storage and processing facilities of CASSM mustalso increase. A given data base may of course be spread over several cells.
CASSM is intended for use with a general-purpose computer acting as a
“ smart” peripheral device. The general-purpose computer accepts the user’scommands or requests, translates these to a set of CASSM instructions, andpasses these instructions to CASSM. The special-purpose device then carries
out the instructions, all cells executing an instruction simultaneously.
Execution of an instruction on CASSM is broken down into three phases:(1) the instruction phase in which an operation is sent to each cell of CASSM,(2) an execution phase in which the instruction is carried out, and (3) a deacti­
vation phase in which the current operation is removed. Each phase requires
one rotation of the disk, but because CASSM is designed to carry out the threeoperations concurrently, one complete operation actually takes place per revo­
lution.
A search for a specific item of information requires that the item pass a test
qualifying it as a potential record of interest. That is, CASSM keeps track of thetypes of records it stores and checks to see if a record is of the proper type. If
the record passes this test, the appropriate field within a record is located andits value examined. Only if all these conditions are satisfied will a record be
retrieved.
For example, a data base may contain information on both automobiles
and owners of automobiles. A search for the records for silver automobiles will
therefore require:
1 A test of the record type to isolate the automobile records
2 Location of the color field for all automobile records
3 Retrieval of the record if the value of the color field is equal to SILVER
Note that this process is conducted for all records in the data base during
the single revolution of a disk (about V60 second).
CASSM is an experimental device and as such exists only as a prototype
and simulator. The design is limited by the necessity to store the entire database on the device. It is not clear whether the processing efficiencies could bemaintained if a data base were to be loaded into CASSM in small segments inseveral different loading operations.
*G

Relational Associative Processor (RAP)

The relational associative processor (RAP) was developed at the University ofToronto as a device for the processing of information specified by a relational
data base model (see Chapter 9). RAP, like CASSM, is a smart peripheral de-ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

325

Main
data
base
store

(a)

Cell N + 1

Data base store(b)
Figure 8-15

The RAP system, (a) RAP system organization, (b) RAP cell organization.

CHAPTER 8326

vice subdivided into cells. Each cell is capable of searching and manipulating
data. The cells are interconnected as shown in Fig. 8-15a so that a cell may
either manipulate data directly in its own storage or may indirectly manipulate
the data in other cells. Each cell contains a buffer to connect the cell processing
unit to the data base, as well as an arithmetic and logical unit and a separate
search and manipulation unit as shown in Fig. 8-15b.
If the data base is small enough to fit within the cell storage areas, then
RAP may be considered to be a multiple processor using direct searches. Whenthe data base is too large for the cell storage, then the search is indirect since
the necessary data must first be transferred from the main data base store. The
latter case is more general; hence RAP is considered a multiple processor in­direct search device.
RAP requires the general-purpose computer to interact with the user for
query or command processing. These must be translated by the general-pur­pose device before they are sent to RAP. In operation, each cell operates simul­
taneously with all other cells by processing the data stored in its memory. Each
information unit which meets the search criteria is then sent to a set function
unit for potential integration with the results from other cells. For example, theset function unit may count the number of information items meeting the search
criteria. The information items eventually selected are delivered to the generalpurpose computer for presentation to the user or for further processing [21 —23].
When the data base is large, RAP is used in conjunction with conventional
disk drives. A section of the data base is moved to a RAP cell at each stage of
operation. That is, a large data base such as the motor vehicle data base for astate government would of necessity be searched in many segments to isolate
the SILVER automobiles.
The RAP operations require that all the information on one track of a disk
be of the same type. That is, the automobile records would be distinct from thedriver records. Thus, the search for the SILVER automobiles will not require atest of the driver records. The process needed to search for SILVER automo­biles will therefore require the following steps:
1 Locating the automobile records
2 Loading the automobile records onto RAP
3 Isolating the color field
4 Retrieving the records with color field equal to SILVER*H

Data Base Computer (DBC)

The data base computer was designed at Ohio State University to manipulatevery large data bases using currently available technology. The DBC is as­
sumed to be connected to a large general-purpose computer for direct inter­action with the user. The retrieval operations are divided into two cycles, in­cluding first the functions that access the data (the data loop) and the functions
associated with the structure of the information (the structure loop) as shown in
Fig. 8-16.

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

327

Host

Figure 8-16 Data base computer organization.

The functions are accomplished by independent modules working on acontinuous stream of data (a pipeline architecture). The central module of the
DBC is the data base command and control processor. This element receives
requests from the general-purpose computer system, translates these requests
to commands for the various functional components of the DBC and controls
the functions of the individual components. When the commands have been ex­
ecuted, the data base command and control processor delivers the requested
information to the general-purpose computer.
The structure loop is composed of four functional units. Together thesefour functions translate a request into a set of physical locations to be searched.
The physical locations are, in fact, blocks of mass storage which contain theinformation items. The data loop has two functional units which access andcheck the information items before they are sent to the general-purpose com­puter.
The structure loop first decodes keywords into one or more file names andfields within the file which must be searched. This is accomplished in the
keyword transformation unit. This translation produces code numbers desig­
nating the addresses of the individual search terms.
The structure memory is, in fact, an inverted file for the data base. An
entry consists of a code number and a series of three numbers of the form
LOGICAL POINTER, CLUSTER NUMBER, SECURITY SPECIFICA­
TION
where (1) the logical pointer identifies a block of information items that are po-

328

CHAPTER 8

tentially relevant, (2) the cluster number is assigned to a record at the time it isentered into the data base and identifies subsets within blocks, and (3) the secu­
rity specification is a simple attribute which is checked prior to the retrieval of
any information.
The results from the structure memory module are then passed to thestructure memory information processor. This device performs Boolean andlogical operations. These operations are performed in a manner similar to that
described for the inverted file operations in Chapter 2. The results of these op­
erations are sets of logical identifiers. These identifiers are passed on to theindex translation unit, which translates them from logical pointers to the physi­
cal addresses of the data items.
If the information is to be directly retrieved, the data base command andcontrol processor passes the physical addresses identified by the index transla­tion unit on to the mass memory. The mass memory also performs Boolean andlogical operations in order to identify the actual information items to be re­trieved. In comparison the structure loop determines which blocks of memory
are to be examined. The mass memory unit selects the appropriate block ofstorage and tests the individual information items to determine which of thesequalify for retrieval.
Once the specific information items have been selected, the security filter
processor sorts the items into a desired order and performs final security
checks to ensure that the user is qualified to receive the items [24,25].
A user request for silver colored automobiles from a data base which
includes both automobiles and licensed drivers might be conducted as follows:
1 The keyword SILVER is passed through the keyword transformation
unit. This converts SILVER into a code which can be used to search the struc­ture memory.
2 The structure memory is searched for all entries with this value. Thissearch is conducted in parallel across all entries. The result is a set of addressesof blocks of records in which at least one record contains the desired value.
3 In this simple search there is no necessity to combine sets so the struc­ture memory information processor simply passes the addresses on to the index
translator unit.
4 The index translator unit is used to convert the logical addresses to spe­cific disk cylinder addresses. These physical addresses are then passed to thedata base command and control computer.
5 The mass memory device (usually a disk) is used to scan the individual
blocks identified by the physical addresses. Each record is scanned for thevalue of its color field, and those equal to SILVER are selected and sent to thesecurity filter, back to the data base command and control processor, and fi­
nally back to the host computer.
I

Other Special-Purpose Devices

Several devices were described in the preceding subsections that are capable ofperforming the entire information retrieval process, or at least major portionsof the process. One can, however, also consider the development of more spe-

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

329

cialized “black boxes” that perform more restricted functions. An especiallyonerous operation is the comparison of lists of items that becomes necessary to
determine the “hits” when Boolean queries are processed with inverted files.
Indeed the lists of documents corresponding to two search terms must then be
merged using set union and set intersection operations when the terms are re­lated by OR and AND operators, respectively. When the document lists are
long, the list processing operations become expensive.
In these circumstances special list merge networks may be useful in which
many of the required operations are carried out in parallel. Consider, in particu­
lar, two lists of n entries each. When a single comparison unit is available capa­
ble of comparing an entry on list 1 with an entry on list 2, at least n sequential
comparison operations are needed to traverse the lists. Alternatively, one canconceive of n comparison units all working in parallel using different elementsof the input lists: the first entry of list 1 might then be compared with the firstentry of list 2 using compare unit 1; the next entries of the two input lists aretreated in compare unit 2, and so on until the last (nth) elements of the lists areprocessed in compare unit n.
The outputs of the initial set of comparisons might be fed in pairs to n/2
additional compare units all working in parallel, followed by n/4 more compare
units on the next level, and so on down to a single unit that compares the final
two elements. When such a network of comparison units is used, the n-element
input lists can be “traversed” in log n steps, instead of the n steps needed forthe single compare unit. Various devices of this type have been proposed andtested in experimental systems [26-28].
Another possibility for effecting savings in retrieval consists in optimizing
the available query statement before initiating a search operation. A query pre­processing system could then be built, designed to check the query for syntac­
tic errors, to reduce the Boolean statements to minimal form, to pretest thequeries against a small database, and to evaluate the usefulness of some searchterms prior to the actual search operation [29]. In situations where information
queries are submitted by users unfamiliar with the retrieval operations a query
preprocessing system might well pay for itself in improved efficiencies when
the final searches are actually conducted.
As an extension of the previously mentioned special-purpose devices, one
might conceive of a whole array of separate devices each designed to optimize
a particular operation such as text scanning, search of inverted indexes, list
merging, and query reformulation. Such an organization might then constitute a
powerful, but probably also expensive, retrieval configuration [30].

3 TEXT ACCESS METHODS*A

Dictionary Search Methods for Static Fifes

In the preceding section various hardware devices were described that may be
useful to store and retrieve large information files. This section examines spe­cific file accessing methods that are of special importance in a bibliographic re-

330

CHAPTER 8

trieval system dealing with natural language texts. The first and most importanttask concerns the search of a dictionary or index to find the entries correspond­
ing to particular query terms. For example, given a library catalog in which theitems are arranged in alphabetical order according to author name, one may
want to find the entries corresponding to particular authors. Alternatively aninverted index file must be searched to determine the location of the lists of
document identifiers corresponding to particular query terms.
Linear Scan Certain file access methods were introduced in Chapter 1.
The present treatment stresses accessing methods that are particularly useful ina dynamic file environment where file additions and deletions must be pro­
cessed together with information retrieval requests. The most obvious file ac­
cessing method that can be used to find a record identified by a particularsearch term consists in performing a linear scan of the complete file, one record
at a time. This method can be used no matter how the file is ordered. However
the traversal time of the complete file will be excessive when the file is large (oforder n for a file of n records). A linear scan is therefore not normally usable inpractice.
Binary Search The next possibility consists in using an access techniquethat eliminates from further consideration at each search step not just one sin­
gle record as in a linear search, but a whole section of the file. The well-known
binary search described in Chapter 1 is a case in point \yhere an ordered file is

Middleelement offirs t eightho f file

Middleelement o flast eightho f file

Figure 8-17 Implicit tree organization of binary search. (Search proceeds to left of node
when KEY < ID and to right of node when KEY > ID.)i

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

331

searched by eliminating one-half of the file still under consideration at eachsearch step. In a binary search the query term, also known as the “key,” is firstcompared with the record in the middle of the file. If the search key is identicalwith the identifier (ID) attached to the middle record, an acceptable record has
been found. Otherwise, one next proceeds to the middle of the top half of thefile if the key is smaller than the record ID, or to the middle of the bottom half if
the search key is larger than the record ID. This process of dividing the file into
two halves continues until an appropriate record is found.
The binary search may be described graphically by a tree as shown in Fig.
8-17. The elements of the ordered file which are compared with the search key
are represented by the tree nodes. Whenever the value of the search key issmaller than the current record identifier, the left path is chosen from the node;conversely the right path is chosen if the search key value exceeds the value ofthe record ID. It is known that tree search strategies of the type illustrated inFig. 8-17 are much faster than linear scans (of order log n instead of n as before)[31-32],A study of the binary search strategy shows that the method used to com­pare the search key with a given record identifier is precisely the same at eachtree node. The only difference in procedure occurring from one node to thenext in the search tree is a redefinition of the portion of the file to be consideredin the search. Let BEG and END designate the addresses of the first and lastelements of the file, respectively, and let the address of the middle element be
defined as MID = [(BEG + END)/2]. The binary search strategy for a given
file F may then be summarized by the four steps of Table 8-2. Assuming that the
search of the complete file is expressed by using parameters (KEY, BEG,
END, FILE F), then the left path of the search tree leads to a new search withparameters (KEY, BEG, MID - 1, FILE F). That is, the end of the file is now
assumed to be the record immediately preceding the middle record of the file.
Moving to the right in the search tree means that the search is next carried out
with parameters (KEY, MID + 1, END, FILE F). That is, the beginning of thefile is now defined as the record immediately following the middle element. A
process like the binary search that is carried out by repeating the same programwith only a change of the parameters used is known as a “recursive” process.
Recursion is an important concept in computing because the automatic equip­
ment is especially useful when the same process can be repeated many times.
Table 8-2
1. If
2. If
3. If
4. If

Outline of Binary Search Program

ID[MID] = KEY
ID[MID] > KEY
ID[MID] < KEY
BEG > END

BIN SEARCH (KEY, BEG, END, FILE F)
Search ends because the wanted element has been foundRepeat binary search with parameters (KEY, BEG, MID - 1, FILE F)
Repeat binary search with parameters (KEY, MID + 1, END, FILE F)
Stop the search because no entry exists in file equal to KEY

BEG: address o f firs t elem ent o f subfile
END: address of last elem ent o f subfile
MID: address of m iddle elem ent of subfile
ID[k]: id entifier o f kth record

332

CHAPTER 8

Estimated Entry Search In the binary search, the next record identifier tobe compared with the search key is chosen at each point from the middle of theremaining subfile. In many cases, it is possible to make a guess about the posi­tion of a file element when its identifier is known. For example, when a normal
dictionary is used to find the word RETRIEVAL, one would certainly not begin
by opening the dictionary somewhere in the middle. Rather one might lookabout two-thirds of the way down because a term starting with the letter R
would occur toward the end of the file. The same is true when trying to findsomeone’s name in the telephone book or a given bibliographic citation in alibrary card'catalog.
When a guess can be made about the likely position of a given record in anordered file, the binary search can be replaced by an estimated entry search,which is similar to a binary search except for the computation of the next rec­ord element to be considered in the search. When good guesses are made about
the position of a wanted record, an estimated entry search will be faster than abinary search (but still of order log n for a file of n items).
Direct Access Search If one knows or can compute the exact position inwhich a wanted record appears in the file, the file can be accessed directly. A
search of order 1 is then carried out instead of order n for a linear scan, or order
log n for a tree search. A well-known direct search method, already discussed
at length in Chapter 2, is the indexed search, where an auxiliary index is used
containing the addresses of the records corresponding to a given search key.
Obviously, there is no need to conduct the search of the main file in these cir­
cumstances, since the needed addresses are obtained from the index. Assumingthat the index search can be performed free of charge— a very unrealistic as­
sumption— only one (order 1) file access is required in the main file to retrieve
the wanted item.
It was mentioned earlier that the creation of an index may be costly be­cause any auxiliary file must be stored and maintained. An alternative wellknown direct file access process, known as a “ hashing,” or “ scatter storage,”
replaces the use of auxiliary indexes by a computation or transformationof the search key into a storage address where the corresponding records are
stored.
One of the problems arising with the use of a hashing system is the choiceof the-hashing function used to transform the search keys into appropriate
memory addresses. In general the number of possible search keys is very large,
whereas the memory space available to store the corresponding record identi­
fiers (known as the “ hash table”) is small. Hence it is necessary to transform alarge number of possible keys into a small number of memory addresses. The
transformation should be done in such a way that the available memory space isevenly used; that is, each memory address should have an equal chance of stor­
ing a given record. Furthermore, clusters of records exhibiting nearly equal
keys should be broken up— for example, records corresponding to the searchkeys HOP and HOPE should not be mapped into the same address.
Two of the best-known hashing methods are the multiplication and divi-

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

333

Table 8-3 Typical Hashing Method Using Key
Multiplication(A ssu m e d H ash T a b le S ize is 64 P o s itio n s )Record M:
Key 11 01 01 00__________
Key squared 1 0 1 0 1 I 1 1 1 1 0 0 I 1 0 0 0 0
Decimal address corresponding to (1 1 1 1 0 0)2 equals
32 + 16 + 8 + 4 + 0 + 0 = 60
Record N:
Key 11 01 01 01
Key squared 1 0 1 1 0 10 0 1 0 0 1
110 0 1
Decimal address corresponding to (0 0
0 0 1)2 equals
0 +0 +8 +0 +0 + 1 =sion hash functions. In the multiplication method the key is multiplied by itself(squared) and the middle digits of the product are used as a record address; inthe division method, the key is divided by a prime number and the remainder
after division is transformed into the needed address [33]. A sample key trans­
formation using the multiplication method is shown in Table 8-3 for two nearly
equal keys using an assumed hash table size of 64 (equal to 26) memory
positions. The two keys are 11010100 and 11010101, respectively, correspond­
ing to the letters M and N in the well-known EBCDIC coding system. The keys
differ in the rightmost binary digit only. The squaring operation produces 16digit binary products. In the example, the middle six binary digits are thentransformed into one of 64 memory addresses by conversion to decimal form.
The record corresponding to key M in Table 8-3 will be located in position 60 of
the hash table, whereas key N is transformed into position 9.
A hashing system (unlike a binary search scheme) can gracefully accom­
modate situations where several records exhibit the same key, because a com­plete bucket of records can be associated with each hash table address, rather
than a single record only. A bucket provides space for several records, buteven when larger buckets are used, collisions are unavoidable for most hashfunctions. A collision occurs when two or more distinct keys are transformed
into the same record address. Collisions will complicate the retrieval process,because the record identifiers found in the designated buckets must be checked
before the corresponding records are actually retrieved from the file. Further­more, collisions may lead to overflow conditions when not enough space exists
to accommodate all the records that must be located in a particular bucket.
Various provisions can be made to handle the overflow: a second hashing oper­
ation can produce a new overflow bucket address located in a secondary hashtable; alternatively, a pointer system can be provided to designate for eachbucket the addresses corresponding to any overflow records. Overflow prob­
lems produce efficiency losses in the hashing system because extra memory
accesses are then required to retrieve the needed records.
*B

Dictionary Search M ethods for Dynamic Files

Dynamic and Extensible Hashing The basic hashing or scatter storage
method described up to now supports searches involving single keys in a static

334

CHAPTER 8

file with few file additions or deletions. Sequential searches that handle the rec­ords in some specified order are difficult to carry out in a hashed file, because
the records are scattered throughout the storage area. The scattering of the rec­ords also destroys any natural clustering properties of the records. For exam­
ple, records identified by the terms CAT and CATS will not be found adja­
cently, even though this might be useful in certain applications.
When the file grows and the original hash table size m becomes too small,
it is necessary to rehash the whole file using a larger hash table size, say of size
2m. The rehashing operation is onerous because all file records must now be
moved in storage. For this reason dynamic or extensible hashing systems havebeen introduced which avoid overflow conditions and the repositioning of rec­ords when the file size grows [34-36]. Various schemes have been proposed: ingeneral an auxiliary index is interposed between the key terms and the final
record addresses in the main file. The hashing operation is then used to identify
an address in the index rather than in the main file, and each index position inturn points to the main file addresses of the corresponding records. Instead ofchanging the main file configuration as new records are added, the index ismade to grow; thus when a given bucket overflows, the corresponding index
entry is changed to produce two entries, corresponding to two new buckets re­placing the single original bucket. Similarly, when the file shrinks, two or more
buckets can be merged into a single bucket by appropriate transformations in
the index. When the index is used as the hash table instead of the main file, aneven use of the index space corresponds to an even use of the full memory
space in the standard hashing system.
Dynamic Tree Search It was mentioned earlier that the basic binary tree
search is not easily adapted to dynamic file conditions. Since the file must be
maintained in ordered sequence according to key values, an insertion of a newrecord into its proper place may cause the displacement of half the records inthe file. Furthermore the tree traversal operation needed to locate the next rec­ord identifier to be matched against the query may be expensive to perform.
Indeed for a file of n records, the binary tree exhibits log2 n levels, and hence
log2 n different record identifiers must be compared with the query key. Since a
new disk seek operation may be needed for each record identifier, the standard
binary tree operation will be expensive to carry out for large files.
This suggests that a tree search could be more efficient when the number oflevels in the search tree is small. The height of the tree, that is, the number oftree levels, can be reduced by packing more than one key value (record identi­fier) into each node of the tree. Furthermore some file growth can be accommo­
dated by leaving space in each tree node for new key values corresponding to
new records added to the file. The best known of the dynamic search trees
obeying these specifications is the so-called B-tree [37-39].
In a B-tree of order d, the root node at the top of the tree contains at least
one key value and two pointers to the next tree level corresponding to keys thatare smaller and larger, respectively, than the original key value. Each node

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

335

other than the root contains at least [d/2] key values and at most d key values.
The number of pointers to the next tree level is one larger than the number ofkeys at the corresponding node. A typical B-tree of order 4 is shown in Fig.
8-18. Each node of the sample tree can in principle accommodate four different
terms, although as few as two terms may actually be used. The number ofpointers to the next tree level varies therefore between 3 and 5. The natural(alphabetic) order of the keys is maintained because the pointer to the left of agiven term is used to find smaller terms than the given key value (that is, occur­
ring earlier in the alphabetic sequence), whereas the right pointer locates larger
terms that are higher in the alphabetic order. For example, the left pointer from
NETWORK locates CATALOG, HARDWARE, and MORPHEME, whereas
the right pointer locates REVIEW and SYNONYM.
A B-tree search is carried out like a binary tree search except that all rec­ord identifiers located at a given node are compared with the available key
values and the appropriate left or right pointers are chosen depending on theoutcome of the key comparisons. For example, when the B-tree of Fig. 8-18 issearched with the query term FILE, the left pointer is taken from node A, fol­
lowed by the pointer located between CATALOG and HARDWARE fromnode B (because FILE is larger than CATALOG, but smaller than HARD­
WARE), followed by the pointer between ENCYCLOPEDIA and GRAMMAR
from node E, and so on.
Since all key values stored in a given node are obtainable in one file access,the maximum number of file accesses is of order logd n for a file of n items,
corresponding to the height of the tree. New keys can be added to or deletedA

FILE

Figure 8-18 Three-level order 4 B-tree (between 2 and 4 keys per node).

CHAPTER 8

336

from a particular node so long as the basic size restrictions are obeyed. How­ever, when a new key value is added to a node of size d, an illegal node of sized + 1 is created. This situation is handled by splitting a node of size d + 1 into
two nodes of size at least equal to [d/2]. Such a splitting operation is shown in
Fig. 8-19 for a B-tree of order 4. The assumption is that the term CLASS must
be added to node B of the tree of Fig. 8-19a. Since this node already contains
four terms, it is split into two pieces, and a new separating term is added to thefather node on the next higher tree level (node A of Fig. 8-19b). Because thefather node has now grown in size by one term, it may itself have to be split.
The node splitting operation may thus propagate upward along the levels of thetree, the maximum number of splitting operations being equal to the height of
the B-tree.
The reverse node merging operation may become necessary when terms
are deleted from a given node. This situation is illustrated in Fig. 8-20 where theterm ENCYCLOPEDIA is deleted from the B-tree of Fig. 8-18. An undersized
node is then produced containing only one term (node D of Fig. 8-20). This
node is merged with its brother (node C of Fig. 8-20) and the term CATALOG,
which is no longer necessary to distinguish the merged nodes, migrates down­
ward by one level. The father node may then become undersized and may inturn have to be merged with a brother. The node merging operation like theearlier splitting operation may thus migrate upward along the B-tree levels.
A

(a)

A

(b)
Figure 8-19 Node splitting operation for B-tree of order 4. (a) Initial condition prior to inser­
tion of CLASS, (b) Condition following bucket splitting after insertion.

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

337

A

(a)

(b)
Figure 8-20 Node merging operation following term deletion, (a) Initial state following dele­tion of ENCYCLOPEDIA, (b) Final state following deletion of ENCYCLOPEDIA.

A search of a B-tree of order d is of order logd n for a file of n records. The
node insertion and deletion operations are also of order logd n, since each oper­
ation may affect at most one node on each tree level. A B-tree implementation
requires more memory space than the conventional hashing system, because
the key values and pointer structures must be kept in storage in order to be
used. A B-tree search is also more time-consuming than a standard hashing op­
eration— typically by a factor of 3 or 4; but the B-tree search is much fasterthan a binary search by a factor of 10 or more. Because of the simple way ofreorganizing the B-trees following insertion and deletion of key values, the Btree search system has become the standard for the implementation of diction­
ary and index search systems in dynamic file environments.
Many other search tree systems have been proposed to handle special situ­
ations. In the well-known digital search trees, or tries, each node of the searchtree is associated with a portion of a key value rather than with a whole key. In
many cases, a small number of tree levels may then be used to accommodate
key values of widely varying length. For example, only three trie levels are

CHAPTER 8

338
C

Figure 8-21 Digital search trees, (a) Initial digital search tree, (b) Digital search tree follow ­ing addition of CODING.

needed to distinguish the terms CAN, CAPE, CATNIP, and CODICIL, assum­
ing that a node is associated with a single key character, as shown in Fig. 8-21a.
The basic trie structure may change drastically when new terms are added asshown in the example of Fig. 8-21b illustrating the addition of the term COD­
ING. However procedures exist for optimizing the representation of digitalsearch trees and for handling term additions and deletions [33,40-41].
*C Multiple Key Dictionary Search

All the foregoing dictionary access methods are usable for single key searches
where only one query key is present. Single key searches are relatively simple
to implement because the existing one-dimensional storage devices can easily
accommodate a file maintained in order according to the single (one-dimen­
sional) key values. In practice, search requests may include many different
keys. For example, one wants to retrieve all the bibliographic records pertain­
ing to a given author and published in a given year, or all the records dealing
with INFORMATION as well as with RETRIEVAL.
The standard access methods, with the exception of systems maintaining
dense (inverted) indexes for each possible key value, are difficult to adapt tomultikey searches. In principle, one can maintain auxiliary indexes covering a
combination of several search terms. For example, given three search terms A,
B, or C, one could maintain seven distinct indexes covering the records per­taining to the keys A, B, and C separately, as well as to the possible term com­binations A and B, A and C, B and C, and A and B and C. When a larger num­
ber of individual terms are present, the number of term combinations ishowever very large, and the task of identifying the most productive term com­binations is difficult [42].

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

339

Another possibility consists in using a superimposed coding system, where
each individual term is encoded by a binary number and the logical union of thevarious component codes designates the term combination. For example, as­suming that CHOCOLATE, NUTS, and VANILLA are identified by codes
100010, 001001, and 100001, the query term CHOCOLATE CHIP COOKIE(assumed to be composed of CHOCOLATE, NUTS, and VANILLA) is repre­
sented as 101011 equal to 100010 v 001001 v 100001 [33].
The superimposed coding system was introduced for retrieval in the wellknown edge-notched card systems some 40 years ago. These systems are un­
fortunately afflicted by the “false drop” problem, where agiven code combina­
tion retrieves many spurious records. Certain term codes may also be included
in other term code combinations. In the previously used example, the term VA­
NILLA is already included in the combination of CHOCOLATE and NUTS. A
longer treatment of term coding systems is unhappily beyond the scope of this
discussion.
D Text Scanning Machines

In addition to the standard dictionary or index searches where table entries cor­
responding to particular keywords or terms must be identified, it may also benecessary in a bibliographic retrieval system to scan linear texts in order to de­termine whether a given phrase or query pattern occurs in the text, and if so
where. Indeed, it was noted in Chapter 2 that some conventional retrieval sys­
tems include options for a so-called string search in which the query terms are
directly compared with document texts or text excerpts. In these circum­
stances, no indexes or auxiliary files need be maintained. Unfortunately, a fulltext scan is normally slow and hence inappropriate for on-line searching. Spe­cial methods and devices have, however, been developed to speed up the text
search process [43-47],
One particular text search device is based on the idea also incorporated
into RAP and CASSM and previously illustrated in Fig. 8-8, in that several
search modules are used to process different portions of the stored texts under
the supervision of a master control computer. Each search module is attached
to a mass storage device such as a disk. When a command is issued by the mas­ter control computer to initiate a text search, each search module begins a se­quential search of its portion of the stored texts. The text read by a search mod­ule is continuously compared with the query statements. When a document isfound that satisfies a particular query statement, a report is sent to a master
control computer which may either directly report the discovery to the user oraccumulate the information for inclusion in a summary report to the user. To
gain speed, the queries can be batched and responses can be generated simulta­
neously for many different queries.
The actual search process may be broken into two parts: (1) term detectionand (2) query resolution. Term detection is concerned with the location ofquery words or pattern in the stored data base. Query resolution is the processof determining if the combination of matches found by the term detection pro-

340

CHAPTER 8

Figure 8-22 Information retrieval machine-searcher organization (several search units at­tached to single master control).

cess matches the term combination specified in the user’s query. For example,
a user may specify that two particular terms must appear in the same document(a Boolean AND operation). Additional search facilities may include term com­binations based on all the Boolean operators previously discussed, as well as
on word proximity, and sentence and paragraph inclusion specifications.
A typical search module for a text scanning machine could then be basedon the use of four special units: a disk controller, term detector, search control
unit, and query resolver, as shown in the diagram of Fig. 8-22. The search con­trol unit carries out data transfer operations, communications between the term
detector and the query resolver, and the general overall control operations forthe search module. The disk controller oversees all access operations to thedisk and the stored information. Equipment of the type represented in Fig. 8-22
can scan text at rates of up to 1 million characters per second using a single
search module only.
**E

String Matching Using the Finite State Automaton Model

A key element in a text scanning system is the term detector which must neces­sarily operate rapidly if large quantities of text are to be processed under opera­
tional conditions. The most simple-minded text scanning system possible isbased on a character-by-character comparison of a given query (key) patternwith a text excerpt (string). The basic procedure consists in comparing the firstcharacter of the query pattern with the first character of the text string. If thesefirst characters match, the second characters are compared, and so on. If any
pair of characters does not produce an exact match, the standard procedure isto shift the query pattern over by one character position and to restart thematching procedure. This becomes expensive because the matching process
must start over near the beginning of the input pattern many times. For exam­
ple, given
query pattern
text string

AAAB
AAAAAABACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

341

16 character comparisons are required before it becomes clear that the four
input characters match the last four characters of the text string. In generalbecause of the backtracking and restart characteristics of the standard text
scanning method, up to m ■n character comparisons may be required in theworst case in order to match a query pattern of length m against a text string oflength n.
Fortunately, more sophisticated approaches to the text scanning problem
exist. Algorithms have been devised that operate in linear or even sublinear
time— that is, the number of character comparisons needed does not exceed(and in fact may be substantially smaller than) the number of characters in thequery and text strings, instead of the square of that number as in the earlier
example [48-50]. These algorithms analyze the query pattern (that is, the query
terms) prior to the actual search operation and construct auxiliary modules ortables to control the actual character comparisons used to match the query pat­terns with the text strings.
A favorite term detection process is based on the concept of the finite state
automaton (FSA) which was introduced in Chapter 7 as a controlling elementin the augmented transition network grammars [26,48,51], An FSA is a concep­
tual machine composed of five basic elements:
1 I— a set of input symbols acceptable to the automaton
2 S— a set of states
3 R— a set of rules which determine the next state of the automaton
given its current state and an input symbol
4 B — a beginning state (an element of S)
5 F — a set of (one or more) final states (elements of S)
It will be remembered from the preceding chapter that the operation of afinite state automaton is representable in diagram form by using nodes (circles)
to represent the individual states and branches (edges) between the nodes torepresent transitions between states. A symbol attached to each branch thenrepresents the element of the set of acceptable input symbols causing the par­ticular transition from one state to the next. Figure 8-23a shows a finite state
automaton with a beginning state 1 and a final state 4. The input symbols ac­
cepted by the FSA are assumed to be the letters of the alphabet, and the sample
automaton of Fig. 8-23a ” accepts“ the input string WIN.
The automaton of Fig. 8-23a handles the string WIN no matter where thatstring occurs in the text; that is, the automaton does not discriminate between
SWINE, WIND, TWIN, and WIN. Furthermore, no instructions are given in
Fig. 8-23a about what happens when the input does not contain the exact letter
string W followed by I followed by N. Clearly, a usable FSA capable of detect­ing complete words in running text must be able to detect word delimiting, orinterword characters, such as blanks that might occur between words; further­more, instructions must be provided about what is to happen when an expectedcharacter is not received at the input. The complete automaton needed to de-

342

CHAPTER 8
Beginning
state

Final
state
W

(a)

(b)

(e)

A C C E S S

T O

IN F O R M A T IO N :H A R D W A R E

A N D

S O F T W A R E

A P P R O A C H E S

343

tect the word WIN is shown in Fig. 8-23b. An interword delimiter is indicatedin that figure by a □ , and an arbitrary character other than one attached to alabeled branch leaving a given state is designated by A- When the string□W IND occurs at the input, the traversal of the automaton from beginningstate 1 to final state 5, and then back to state 2, is straightforward. If the input
consists of DWOND, the normal transitions would occur from state 1 to states
2 and 3. At that point, the input character is an O; the three branches out ofstate 3 are labeled I, □ , and A , respectively. Since the letter O is neither I nor□ , the A exit is taken from state 3 back to 1, where the automaton is now
prepared anew to recognize DWIND. The recognition process also fails for the
input DWINTERD, because the path taken from state 5 returns to state 1
rather than back to state 2 via the output label “ WIN.”
A single automaton can be built for the detection of several query words.
The graph of Fig. 8-23c presents an FSA capable of detecting WIN and WON.
The alternative exits back to state 2 when a □ occurs, or back to state 1 for theoccurrence of any character other than one already attached to a branch (A),are omitted in Fig. 8-23c. The full construct including the upper (A) and lower(□) exits is similar to that of Fig. 8-23b.
The automaton of Fig. 8-23c could be simplified by eliminating one state, if
the string W?N were to be recognized, where ? represents exactly one arbitrary
character. The corresponding automaton is shown in Fig. 8-23d. Note that thelabel ? is not identical with A >since ? represents any character other than □ ,whereas A represents the default exit taken for any character other than one
attached to a label. The automaton of Fig. 8-23d recognizes WAN, WIN,
WON, or for that matter WNN, WZN, etc.
Suppose that one were interested in recognizing patterns such as WIN,
WON, WOMAN, WOMEN, or in general the sequence W*N where * repre­
sents any character string of arbitrary length. The automaton needed for thispurpose is no more complicated in principle than the one used for the recogni­tion of “ WIN” in Fig. 8-23b; it is shown in Fig. 8-23e. The main difference be­
tween Fig. 8-23e and b lies in the recognition of the arbitrary string of “don’tcare” characters. This requires a redefinition of the default state chosen when aspecifically labeled character does not occur as expected. In the example ofFig. 8-23e the initial default state is state 1. That is, if the input consists of SIN
instead WIN, one returns to state 1 from state 2 when the S occurs at the input
instead of the expected W. After state 4 is reached following the input of char­acters □ , W, and ?, the default state for A characters is now changed to state 4.
At that point the W has already been recognized, and any arbitrary string end­
ing in N is now acceptable following the W. A slight complication arises forstrings that include several N ’s following the initial W, as in WINN, or WIN-

Figure 8-23 (opposite) Finite state automata used for string recognition, (a) Basic automaton
for detection of WIN. (b) Complete automaton for detection of WIN. (c) Automaton for detec­tion of WIN and WON. (d) Automaton for detection of W?N. (e) Automaton for detection of
W*N.

344

CHAPTER 8

1
2
Current , 3
state

5

□
2
2
2
2

#

W

I

N

1
1
1
1
1

1

1
1

1
1
1

3

1
1
1

4

1
1

5

1

Figure8-24 Tabular
representation
specifying new state given current stateand input symbol for finite state automaton of Fig. 8-23b.

NIN. The appropriate pointers to handle these cases are included in the graphof Fig. 8-23e.
A general finite state automaton can be defined for any user-specified
string of symbols. The state transitions may be represented in each case by atable using the current state as input and specifying the corresponding next
state for each acceptable input symbol. An example is shown in Fig. 8-24 forthe automaton of Fig. 8-23b. The tabular representation of the finite state au­
tomaton can be used for rapid comparisons of an arbitrary incoming text withquery terms previously encoded into the automaton.
In principle a separate automaton can be used for each individual term in aquery. Several automata can also be combined for the detection of groups ofterms and of contiguous terms. Thus, two given automata A and B could eachsearch for a distinct term. The results of the comparison for A and B might bepassed on to a new automaton C. When the two search terms are not expected
to occur contiguously in the input text, the search results are directly passed on
to the output device. Otherwise, automaton C is used to verify the text contigu­
ity condition. The organization of the several finite state automata is illustrated
in Fig. 8-25 [47-49],
The main problem encountered in the use of finite state automata for text
scanning purposes is the need to build and maintain the transition structures foreach incoming query. When new queries are continuously submitted to a re­trieval system, the overhead inherent in the construction of the transition ma­
trices may lower the efficiency of the process for operational use. On the other
hand, if the query set remains constant over long periods of time—-such as insystems for the selective dissemination of information— the state transition
matching process is straightforward and efficient.
Detects single words

To queryresolverDetects
single words

Figure 8-25

Multiple term detection using finite state automaton.

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

345

Various other efficient text scanning methods have been developed in thelast few years [49-50]. The Boyer and Moore method is one of the most attrac­
tive ones. It is briefly described in the next subsection.
**F

The Boyer and Moore String Matching Method

Like the previous FSA string detection system, the Boyer and Moore (BM)method depends on a prior analysis of the query pattern [50]. Specifically to use
the BM process it is necessary to construct an auxiliary table including the po­sitions in the pattern for all individual characters, as well as for all contiguous
character strings consisting of more than one character.
Consider, for example, the input
1 2 3 4 5 6
B A N A N A
A character position number may be used to designate the place of each charac­
ter in the pattern. The pattern analysis would note that character B occurs inposition 1, character A in positions 2, 4, arid 6, and character N in positions 3
and 5. Furthermore the pair AN occurs in positions 2 ,3 , and 4,5; NA occurs in
3, 4, and 5, 6; ANA occurs in positions 2, 3, 4, and 4, 5, 6; and so on. The
position information is used later to determine the place where a matching op­
eration must be restarted once a mismatch between characters has occurred.
The BM algorithm proceeds by first comparing the rightmost (rather thanthe leftmost) character in the pattern with a particular character in the string. If
a match is found, a left shift is made and the character to the left of the right­
most pattern character is treated. A string pointer is used to designate the string
character that must currently be matched with the given pattern character. This
pointer is moved left by one character position when a match occurs; when acharacter mismatch occurs, the string pointer is moved to the right so as to des­ignate the next string character to be compared with the rightmost pattern char­acter. The principal complexity in the BM algorithm consists in determining ex­
actly the pointer shift (in number of string characters to be skipped) in the eventof mismatch.
Two principal rules are used to specify the permissible pointer shift when amismatched character is detected:
1 When a mismatched string character is detected, an attempt is made tofind that string character elsewhere in the pattern, and to determine the pattern
shift necessary to achieve coincidence (known as the Ax shift); should the string
character not occur in the pattern at all, a shift by the whole length of the pat­tern is in order.
2 When a portion of the pattern matches some substring in the text, anattempt is made to find a repeating occurrence in the pattern of the originallymatching subpattern; the shift needed to bring the new occurrence of the sub­pattern in coincidence with the matching substring is known as the A2 shift.

CHAPTER 8

346

In order to detect a complete match between a query pattern and a pattern of
the text string, the conditions giving rise to the Aj and A2 shifts must both besatisfied, because a mismatched string character must eventually find a matchin the pattern (hence the Ax shift), and an already matching part of the patternmust again be matched following a pointer shift operation (hence the A2 shift).
At each point in the matching process it is then appropriate to execute a shiftequal to the maximum between Ax and A2.
Consider the following query pattern and text string:1 2 3 4 5 6 7 8 9Pattern: c b a a b c a b c
String: a b c d e f a b c a b c d e f a b c .

. .

t yyy
After a successful comparison between the ninth (last), eighth and seventhcharacters, a mismatch is found in the sixth character position. At this point,
two pattern shifts are possible. Consider the Aj shift first: Since the mismatchedstring character f occurs nowhere in the pattern, the pattern can be shifted all
the way beyond the f character position, producing the following new situation:
Pattern:c b a a b c a b c
String: a b c d e f a b c a b c d e f a b c .

T. .

The A2 shift is determined by finding a new occurrence of the matching subpat­
tern abc in positions 7 to 9. Since the abc subpattern is repeated in pattern posi­tions 4 to 6, a shift of 3 will maintain the match with the originally matching
substring:P:c b a a b c a b c
S: a b c d e f a b c a b c d e f a b c

y yy

t

Since the largest possible pointer shift is most advantageous, the Aj shift is exe­
cuted in the case under consideration. A full example of the BM process is in­cluded in Fig. 8-26 [52],
It is easy to see that the number of required character matches between
strings and patterns will decrease as the differences between the text string andquery patterns increase (that is, as fewer string characters occur in the pattern)
and as the pattern exhibits fewer repeating portions. Normally, the number ofcharacter mismatches is much larger than the number of character matches. In
such a case, the number of character comparisons will be substantially less thatthe text string length, and the BM process will prove particularly efficient. A
disadvantage of the BM process is that embedded !‘don’t care” characters oc­
curring in the middle or at the end of the query patterns are difficult to handle.

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

1 2 3 4 5 6
P : BANANAS :l-W A N T -T O -F L A V O R -N A T U R A L -B A N A N A St(a) T=/=A and T does not occur in pattern : shift by pattern length.
P :S :BANANA
1-W A N T -T O -F L A V O R - N A T U R A L - B A N A N A St(b) Lt* A and L does not occur in pattern : shift by pattern length.
B A N ANAP :S :1-W A N T -T O -F L A V O R - N A T U R A L - B A N A N A St(c) N #A , but N occurs in pattern; to bring N in coincidence w ith next
occurrence in pattern, A, sh ift = 1.
P :BANANAS :I - W A N T -T O -F L A V O R -N A T U R A L-B A N A N A St / /(d) NA matches NA, but -=AA; next occurrence o f NA in pattern is in
positions 3 and 4 o f pattern; to bring matching parts in coincidence
A2 shift = 2; since nonmatching string character does not occur inpattern, can shift pattern beyond - ; that is A, shift = 4
B ANANAP :S :I-W A N T -T O -F L A V O R -N A T U R A L -B A N A N A St /(e) A matches A, but R#N and R does not occur in pattern;
A 2 shift = 2 to reach next occurrence o f A in pattern;
A , shift = 5 to shift beyond R.
BANANAP :S :I-W A N T -T O -F L A V O R -N A T U R A L -B A N A N A St(f)

N # A , A, shift = 1 to reach next occurrence o f N in pattern.
BANANAP :S :I-W A N T -T O -F L A V O R -N A T U R A L -B A N A N A S
t /

/ /

<9> A N A = A N A but B=AN; fo r next occurrence o f A N A in pattern A2
shift = 2; fo r next occurrence o f nonmatching string character B,
A, shift = 2.
BANANAPS :I-W A N T -T O -F L A V O R -N A T U R A L -B A N A N A S/ / / / / /(h) Complete match.

Figure 8-26

Sample pattern match using BM process.

347

348

CHAPTER 8

Don’t care conditions occurring at the beginning of the queries do not, how­ever, pose any special problems.
In operational environments, a decision on what process to choose for text
matching purposes must depend on a comparison between the programmed
string matching methods and the previously described special-purpose hard­ware devices or information retrieval machines that may be available for use.
4

SUMMARY

The purpose of this chapter has been to present actual information retrieval
hardware devices and processing methods and to mention some new possibili­ties for information retrieval implementation in a changing technological en­
vironment. Technological changes have raised the possibility of greatly in­creased processing efficiencies. One of the most significant of these changes is
the movement of some of the processing power to specialized data storage de­vices. That is, through the use of smart peripherals, the quantity of informationthat must be transferred from one storage device to another may be reduced.
Information is examined where it is stored, and only that portion passing theinitial screening is actually transferred for additional processing.
Second, there is interest in the development of specific devices for certain
information retrieval tasks. Each step in the information retrieval process may
be analyzed and special devices may help to carry out the individual steps. The
result may be a series of special-purpose devices that collectively constitute a
powerful retrieval system.
In addition to the special-purpose hardware, efficient data structures andfile access procedures have been introduced which perform dictionary andindex table searches in a dynamic file environment with a minimum of file rear­
rangement. The dynamic hashing and B-tree file search procedures are espe­
cially attractive in this connection.
Finally, new text matching methods implemented by hardware or by soft­
ware programs can now be used for a fast scanning and detection of character
patterns in running texts. These text scanning systems may in time be used tofind answers to queries by a direct examination of the texts rather than by theconventional inverted file processing.
Whether these developments will find favor with the users and managers of
retrieval systems ultimately depends on their economic viability as well as on
their ease of use and effectiveness. One may expect results from practical testsof the new methodologies within the next few years.
REFERENCES[1] W. Durant, T h e Story o f C ivilization: Part 1, Our Oriental H eritage, Sim on andSchuster, N e w Y ork, 1954.
[2] W .L . Schaaf, editor, Our M athem atical Heritage: E ssa y s on the Cultural Signifi­
cance o f M athem atics, Collier B o o k s, N e w Y ork, 1963.

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

349[3] M . B oh l, Information P rocessing, 2nd Edition, S cien ce R esearch A sso cia tes, Chi­cago, Illinois, 1976.
[4] V . B ush, A s W e M ay Think, A tlantic M onthly, V ol. 176, N o . 1, 1945, pp. 101-108.
[5] L .C . Sm ith, “ M E M E X ” as an Im age o f Potentiality in Information Retrieval R e­
search and D evelop m en t, Third International Information Retrieval C onference,
Cambridge, England, June 1980.
[6] N . K nottek, Mini and M icrocom puter Survey, D atam ation, V ol. 24, N o . 8, A ugust
1978, pp. 113-124.
[7] T.C . Chen, Com puter T echnology and the D atabase U ser, IBM Corporation, R e­
search R eport RJ-2316, San Jose, California, A ugust 1978.
[8] P.W . W illiam s, T he Potential o f the M icroprocessor in Library and Information
W ork, A slib P roceedings, V ol. 31, N o . 4, April 1979, pp. 2 0 2 -2 0 9 .
[9] A .D . Pratt, T he U se o f M icrocom puters in Libraries, Journal o f Library A utom a­tion, V ol. 13, N o . 1, M arch 1980, pp. 7 -1 7 .
[10] F .G . W ithington, B eyon d 1984: A T echnology F orecast, D atam ation, V ol. 21, N o .
1, January 1975, pp. 5 4 -7 3 .
[11] B. Parhami, A H ighly Parallel Computing System for Inform ation R etrieval, Pro­
ceedings o f the Fall Joint Computer C onference, A FIPS P ress, M ontvale, N e w Jer­
sey , 1972, pp. 6 8 1 -6 9 0 .
[12] R .S. R osenthal, T he D ata M anagem ent M achine— A C lassification, Proceedings o f
Third W orkshop on Computer A rchitecture for N on-N um eric P rocessing, A sso c ia ­tion for C om puting M achinery, N e w Y ork, M ay 1977, pp. 3 5 -3 9 .
[13] O. Bray and H .A . Freem an, D ata B ase Com puters, L exington B o o k s, L exington,
M assachusetts, 1979.
[14] C .C. F oster, C om puter A rchitecture, E ncyclopedia o f Com puter S cien ce, A . Ral­ston and C .L . M eek, editors, Petrocelli/Charter, N e w Y ork, 1976, pp. 2 6 3 -2 6 8 .
[15] P .B . Berra, D ata B ase M achines, ACM SIGIR Forum , V ol. 12, N o . 3, W inter 1977,
pp. 4 -2 2 .
[16] K .E . B atcher, ST A R A N Series E , Proceedings o f the 1977 International C onfer­
en ce on Parallel P rocessing, A ugust 1977, pp. 140-143.
[17] A .L . R obinson, Array Processors: M axi-Num ber Crunching for a Mini Price, S ci­
en ce, V ol. 203, 12 January 1979, pp. 156-160.
[18] C .N . W inningstad, Scientific Computing on a Budget, D atam ation, V ol. 24, N o . 10,
O ctober 1978, pp. 159-173.
[19] G. Salton and D . Bergmark, Parallel C om putations in Inform ation R etrieval, in
Lecture N o te s in C om puter S cien ce, V ol. I l l , W. Handler, editor, Springer Verlag,
B erlin-N ew Y ork, 1981, pp. 32 8 -3 4 2 .
[20] G .P. C opeland, C.J. L ipovski, and S .Y .W . Su, The A rchitecture o f CASSM : A
Cellular S ystem for N on-N um eric P rocessing, P roceedings o f the First Annual
Sym posium on Computer A rchitecture, A ssociation for Computing M achinery,N ew Y ork, D ecem b er 1973, pp. 121-125.
[21] P. J. Sadow ski and S. A . Schuster, E xploiting Parallelism in a Relational A ssociative
P rocessor, Proceedings o f the Fourth W orkshop on C om puter Architecture for
N on-N um eric P rocessin g, A ssociation for Computing M achinery, N ew Y ork, A u­gust 1978, pp. 9 9 -1 0 9 .
[22] S .A . Schuster, H .B . N gu yen , E .A . Ozkarahan, and K .C . Sm ith, R A P2— A n A sso ­ciative P rocessor for D ata B ases and Its A pplication, IE E E Transactions on C om ­puters, V ol. C-28, N o . 6, June 1979, pp. 4 4 6 -4 5 8 .
[23] S .A . Schuster, H .B . N gu yen , E .A . Ozkarahan, and K .C . Sm ith, R A P2— A n A sso -350

CHAPTER 8

ciative P rocessor for D ata B a ses, P roceedings o f the Fifth A nnual Sym posium on
Computer A rchitecture, A ssociation for Computing M achinery, N e w Y ork, April
1978, pp. 5 2 -5 9 .
[24] D .K . H siao and K . Kannan, T he A rchitecture o f a D atabase Com puter— A Sum ­mary, Proceedings o f the Third W orkshop on Computer A rchitecture for N o n -N u ­m eric P rocessin g, A ssociation for Computing M achinery, N e w Y ork, M ay 1977,
pp. 3 1 -3 4 .
[25] D .K . H siao, K . K annan, and D .S . Kerr, Structure M em ory D esigns for a D atabase
Computer, P roceedings o f the ACM ’ l l N ational C onference, A ssociation for C om ­puting M achinery, N e w Y ork, O ctober 1977, pp. 3 4 3 -3 5 0 .
[26] L .A . H ollaar, T ext Retrieval Com puters, Computer, V ol. 12, N o . 3, March 1979,
pp. 4 0 -5 0 .
[27] L .A . H ollaar, A D esign for a L ist M erging N etw ork , IE E E T ransactions on C om ­puters, V ol. 28, N o . 6, June 1979, pp. 4 0 6 -4 1 3 .
[28] W .H . Stellhorn, A n Inverted File P rocessor for Information R etrieval, IE E E Trans­
actions on C om puters, V ol. C-26, N o . 12, D ecem ber 1977, pp. 1258-1267.
[29] S .E . P reece, D esign for a M odular Query Pre-Processor S y stem , Proceedings o f the
A nnual M eeting o f the American S o ciety for Information S cien ce, Am erican S o ­ciety for Inform ation S cien ce, W ashington, D C ., 1974.
[30] L .A . Hollaar and D .C . R oberts, Current R esearch into Specialized P rocessors forT ext Inform ation R etrieval, Proceedings o f the 4th International C onference on
V ery Large D ata B a ses, Septem ber 1978, pp. 27 0 -2 7 9 .
[31] C .E . Price, Table L ook-up T echniques, Computing S u rveys, V ol. 3, N o . 2, June
1971, pp. 4 9 -6 5 .
[32] W .A . Burkhard and R .M . K eller, Som e A pproaches to B est-M atch File Searching,
C om m unications o f the A CM , V ol. 16, N o . 4, April 1973, pp. 2 3 0 -2 3 6 .
[33] D .E . K nuth, T he Art o f Programming, V ol. 3: Searching and Sorting, A ddison
W esley Publishing C om pany, R eading, M assachusetts, 1973.
[34] M. Scholl, N e w F ile Organizations B ased in D ynam ic H ashing, ACM Transactions
on D atabase S y stem s, V ol. 6, N o . 1, M arch 1981, pp. 19 4 -2 1 1 .
[35] R. Fagin, J. N ievergelt, N. Pippenger, and H .R . Strong, E xtendible H ashing— AF ast A ccess M ethod for D ynam ic F iles, ACM T ransactions on D atabase S ystem s,
V ol. 4, N o . 3, Septem ber 1979, pp. 3 1 5 -3 4 4 .
[36] P. A . L arson, D ynam ic H ashing, B IT , V ol. 18, 1978, pp. 184-201.
[37] D . Comer, T he U biquitous B -T ree, Computing Surveys, V ol. 11, N o . 2, June 1979,
pp. 121-137.
[38] J. N ievergelt, Binary Search T rees and File Organization, C om puting Surveys, V ol.
6, N o . 3, Septem ber 1974, pp. 195-207.
[39] R. B ayer and E . M cCreight, Organization and M aintenance o f Large Ordered In ­d ex es, A cta Inform atica, V ol. 1, N o . 3, 1972, pp. 173-189.
[40] E .H . Sussenguth, Jr., The U se o f Tree Structures for P rocessing F iles, Com m uni­
cations o f th e A C M , V o l. 6, N o . 5, M ay 1963, pp. 2 7 2 -2 7 9 .
[41] E. H orow itz and S. Sahni, Fundam entals o f Data Structures, Computer S cien ce
Press, W oodland H ills, California, 1976.
[42] V .Y . Lam , M ultiattribute R etrieval w ith Com bined In d ex es, C om m unications of
the A C M , V ol. 13, N o . 11, N ovem b er 1970, pp. 6 6 0 -6 6 5 .
[43] A . E l M asri, J. R ohm er, and D . T usera, A M achine for Inform ation R etrieval, Pro­
ceedings o f the Fourth W orkshop on C om puter A rchitecture for N on-N um eric Pro­
cessing, A ssocia tio n for Computing M achinery, N e w Y ork, A ugust 1978, pp. 117—

120.

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

351[44] D .C . R oberts, A Specialized C om puter Architecture for H igh Speed T ext Search­ing, Second W orkshop on Computer Architecture for N on-N um eric Processing,A ssociation for Com puter M achinery, N e w Y ork, 1976.
[45] R .M . Bird, J.B . N ew sb au m , and J.L . T refftzs, T ext File Inversion: An Evaluation,
Proceedings o f the Fourth W orkshop on Computer A rchitecture for N on-N um ericP rocessing, A ssocia tio n for Computing M achinery, N e w Y ork, A ugust 1972, pp.
4 2 -5 0 .
[46] R .M . Bird, J.C. T u, and R .M . W orthy, A ssociative/Parallel P rocessors for Search­
ing V ery Large Textual D ata B a se s, P roceedings o f the Third W orkshop on C om ­puter A rchitecture for N on-N um eric P rocessing, A ssociation for Computing M a­chinery, N e w Y ork, M ay 1977, pp. 8 -1 6 .
[47] D .C . R oberts, A Specialized Computer Architecture for T ext R etrieval, P roceed­
ings o f the Fourth W orkshop on Computer Architecture for N on-N um eric Pro­
cessin g, A ssociatio n for Computing M achinery, N ew Y ork, A ugust 1978, pp. 5 1 59.
[48] A .V . A ho and M .J. Corasick, E fficient String Matching: A n A id to Bibliographic
Search, C om m unications o f the A C M , V ol. 18, N o . 6, June 1975, pp. 33 3 -3 4 0 .
[49] D .E . K nuth, J.H . M orris, and V .R . Pratt, F ast Pattern M atching in Strings, SIAM
Journal o f C om puting, V ol. 6, N o . 2, June 1977, pp. 3 2 3 -3 5 0 .
[50] R .S. B oyer and J.S . M oore, A F ast String Searching A lgorithm , Com m unicationso f the A CM , V ol. 20, N o . 10, O ctober 1977, pp. 7 6 2 -7 7 2 .
[51] R. H askin, Hardware for Searching Very Large T ext D atab ases, Proceedings o f
Fifth W orkshop on Computer A rchitecture for N on-N um eric P rocessing, A sso cia ­tion for C om puting M achinery, N e w Y ork, M arch 1980, pp. 4 9 -5 6 .
[52] G. Salton, A utom atic Information R etrieval, Com puter, V ol. 13, N o . 9, Septem ber
1980. pp. 4 1 -5 6 .

BIBLIOGRAPHIC REMARKSThe following texts contain introductory descriptions of information technolo­gies:
M .B ohl, Inform ation P rocessing, 2nd E dition, S cien ce R esearch A sso cia tes, Chicago,
Illinois, 1976.This is a good introduction to com puter sy stem s, providing a large
number o f illustrations for ea sy visualization o f the various d ev ices and their u ses.
J.G. Burch, Jr., and F .R . Strater, Jr., Inform ation S y stem s— T heory and Practice, 2nd
E dition, Ham ilton W iley C om pany, Santa Barbara, California, 1979. T he appendix
to this text provides an excellen t short introduction to information technologies.

More advanced descriptions of computer hardware are included in:
D .P . Siew iorek, C .G . B ell, and A . N ew ell, C om puter Structures: Principles and E x ­am ples, M cGraw-Hill B o o k C om pany, N e w Y ork, 1982, 926 pages.
H .W . G schwind and E .J. M cC luskey, D esign o f Digital C om puters— An Introduction,
2nd E dition, Springer V erlag, N e w Y ork, 1975.
G .A . K orn, M inicom puters for E ngineers and Scien tists, M cGraw-H ill B ook Com pany,
N ew Y ork, 1973, 303 pages.

352

CHAPTER 8

The development of information technologies for applications such as in­formation retrieval is often covered in workshop proceedings such as those on
Computer Architecture for Non-Numeric Processing published by the Associa­
tion for Computing Machinery. Many of the developments from these confer­ences are synthesized in a single text:
O. Bray and H .A . Freem an, D ata B ase Com puters, L exington B o o k s, L exington, M as­
sachusetts, 1979.

A variety of journals regularly cover new hardware development, includ­ing in particular the journals published by the Computer Society of the IEEE
(Institute of Electrical and Electronics Engineers). Of particular interest is thereadable Computer, and the more technical IEEE Transactions on Computers.
Software procedures useful for dictionary access and text processing often ap­
pear in literature published by the Association for Computing Machinery, nota­
bly the Communications o f the ACM and the ACM Transactions on Database
Systems.
EXERCISES
8-1

8-2

In information processing the main file characteristics, such as file size and record
contents, norm ally determ ine the storage medium used to maintain the records as
w ell as the file a cc e ss m ethods. T hus, a file o f 100 bibliographic records each d e ­scribed by author nam e, docum ent title, journal nam e, volu m e number, date o fpublication, pagination, and short abstract m ay best be accom m odated on a set o f 3
by 5 index cards that are manually searched to find a given item . Card storage is
inexpensive; the file is easily updated, and rapid file searches are p ossib le w hen thefile size is sm all. A s the file grow s, a manually a ccessed card file necessarily b e ­com es less advantageous. D escribe the desirable characteristics o f an autom atic
device capable o f storing and manipulating each o f the follow in g files:a A file o f 1,000 bibliographic records organized sequentially according to the al­phabetic ordering o f the title. T he file is m oderately a c tiv e — that is, a fair num ­ber o f searches are conducted; but the volatility is lo w — there are fe w additions
and d eletion s.
b A file o f 1,000,000 records stored in random order. T he file is very active but o f
low volatility.
c A file o f 1,000,000 records stored in random order.The file is active as w ell as
volatile.
d A file o f 1,000,000,000 records stored in random order. The file is m oderately
active, but w ith relatively few additions and deletion s.
A s the technology used to store a given file o f records ch an ges, conversion co sts
are incurred in the changeover from one m edium to another. For exam ple, the co n ­version o f a manual file into a com puter-based file m ay entail a co stly keypunching
operation to transfer the original inform ation onto punched cards from where theinformation can in turn be transferred onto tape or disk. Identify the problem s andco sts incurred in the follow ing changes o f storage tech n ology for a given file o f rec­ords:

ACCESS TO INFORMATION: HARDWARE AND SOFTWARE APPROACHES

353a

M agnetic tape to m agnetic disk
M agnetic disk to associative array storagec M agnetic disk to data base com puter
Changes in storage technology m ay produce advantages in the accessing and file
updating operations. Identify the benefits obtained from the file conversions listed
in E xercise 8-2.
D escribe in flowchart form the com p lete p rocess used to answ er the follow ing
queries:

b

8-3

8-4

(1)
(2)
(3)

8-5

8-6

8-7

TERM A A N D TERM B
TERM A NOT. TERM B
TERM A W ITH TERM B(W ITH = in sam e sen ten ce as)

A ssum e that the follow ing storage tech n ology is used to store the corresponding
file o f records:
a A n associative array processor such as the Staranb The data base com puter
Three main characteristics m ay b e identified that are o f primary im portance in in­form ation retrieval:a The file searches should be efficient as w ell as effective,b The user interface should permit a relatively effortless interaction betw een userand system .
c T he storage medium should accom m odate files o f substantial size.
D escribe m ethods arid techniques capable o f accom m odating th ese various a im s.1
Are there lim itations indicating that the stated requirem ents cannot all be m etsim ultaneously by a single system ?
C onsider three retrieval system s w ith the follow ing sets o f keywords:a B A T , C A T , H A T , M A T, SA T
b F A IR , F A IT H , F A L L , F A M E , F A N , F A N C Y
c H E , S H E , H E R , H E R E , T H E R E , SH E A R
For each keyw ord system , construct a system o f finite state autom ata capable o frecognizing the various keyw ords in a tex t scanning system . Can you think o f am ethod w hereby a single set o f states is used to store repeating portions o f the vari­
ous k eyw ord s— for exam ple, the ending A T in part a or the seq u en ce FA in part b?
U se the B oyer-M oore m ethod to com pare the keyw ord F A N C Y with the docum ent
title “ F A N A T IC F A N N Y FA R M E R ST R U C K M Y F A N C Y .” S h ow all steps andexplain each o f the required character shifts. H o w many character com parisons areneeded to obtain a com plete match?