Chapter 2

Systems Based on
Inverted Files

0 PREVIEW

This chapter covers the operations of retrieval systems based on inverted files.
The effect of the main Boolean operators that are used in many information
retrieval environments is first described, followed by an examination of adja­
cency and term frequency operations. Selected features from the available
commercial information retrieval systems are then described. Finally enhance­
ments are considered to the basic inverted file design.
'
1 GENERAL CONSIDERATIONS

It was indicated in Chapter 1 that virtually all the commercially available sys­
tems are based on inverted file designs [1]. That is, each system logically con­sists of a document file and one or more auxiliary directories known as the “in­verted index.” The inverted index contains the allowable indexing terms. For
each term an associated list of document reference numbers is included in theindex [2]. Each document reference number uniquely specifies a document towhich a given term has been assigned. Thus, the retrieval of the documents
identified by an arbitrary term requires a search of the index to find the desired
24

SYSTEMS BASED ON INVERTED FILES

25

term, and hence the associated document reference numbers. Finally the iden­tified documents are selected from the document reference file. This simple
process carries out the functions of the SIMILAR operation introduced in
Chapter 1 when single-term queries are processed. In practice, query state­ments consisting of a single term are rarely used. Occasionally a single term
may be sufficiently new or unique to make it a reasonable query all by itself [3],An example of a term which may fit this criterion is “videodisc.” However, by
the time this text is published, many thousands of references may already exist
even for such a specialized term.
A

Boolean Expressions

Normally the searcher has to restrict the number of items retrieved by a search
to fewer documents than are found by using a single term. For instance, theterms “information” and “retrieval” may be separately included in the in­verted index. The person searching for references to the concept “information
retrieval”would like to ensure that the retrieved documents are at least identi­
fied by both terms. The assumption is that documents that include both terms
may in fact be about the topic “information retrieval” [4], The SIMILAR func­tion of Chapter 1 is then interpreted as requiring the presence of both query
terms to select a given document as potentially useful.
To identify those documents containing both the term “information” andthe term “retrieval,” it is necessary to process only the information from theinverted index rather than the information from the document file. Boolean
logic is used to construct queries consisting of a variety of terms using the Boo­lean operators AND, OR, and NOT [5]. These operations are implemented byusing set intersection, set union, and set difference procedures, respectively.
One query which may be used to identify documents on “information retrievaF’may be stated as
INFORMATION AND RETRIEVALThe following procedure might then be used to find the corresponding docu­
ments:
1 Use the inverted index to retrieve the document reference numbers as­sociated with the term INFORMATION. Call these document reference num­bers Set 1.
2 Use the inverted index to retrieve the document reference numbers as­sociated with the term RETRIEVAL. Call these document reference numbers
Set 2.
3 Determine which document reference numbers constitute the intersec­
tion of Sets 1 and 2, that is, are contained in both Set 1 and Set 2. Call these
document reference numbers Set 3.
4 Use the main document file to retrieve the documents identified by the
document reference numbers in Set 3.

CHAPTER 2

26

In other words, documents included as members in both Set 1 and Set 2 (the set
intersection) are those that satisfy the query and are to be retrieved.
The query
INFORMATION OR RETRIEVAL
refers to documents which are identified either by the term INFORMATION orby the term RETRIEVAL or by both terms. Set 1 and Set 2 may be determinedin the same manner as for the AND operator. These sets are then combined
into a new Set 3 which contains an identifier for each document contained ineither Set 1 or Set 2 or in both sets (set union). Any document included in thiscomposite set is then retrieved by the query statement.
The NOT operator is usually implemented as an operator which specifies
that some particular term is to appear in the retrieved document but that someother term is not allowed to appear. For instance, the query statement
INFORMATION NOT RETRIEVAL
refers to documents containing the term INFORMATION but not containing
the term RETRIEVAL. In order to accomplish the negation operation using an
inverted file system, the following procedure may be used:
1 Use the inverted index to retrieve the document reference numbers as­sociated with the term INFORMATION. Call these document reference num­bers Set 1.
2 Use the inverted index to retrieve the document reference numbers as­sociated with the term RETRIEVAL. Call these document reference numbers
Set 2.
3 Remove from Set 1 any document reference number included in Set 2.
That is, construct the set difference between Sets 1 and 2.
4 Use the document file to retrieve the documents indicated by the docu­
ment reference numbers remaining in Set 1.
In other words, the documents that satisfy the query statement have reference
numbers contained in Set 1 but not in Set 2 (set difference).
B Order of Operations

The complexity of a query can grow substantially as new operators are added,
and a variety of rules are necessary to ensure that queries submitted by thesearcher are interpreted correctly by the retrieval system. Consider as an ex­
ample the inverted index as shown in Table 2-1. A query such as
APPLE AND ORANGE OR BANANA
is ambiguous. If one starts at the left of the query statement and works toward

SYSTEMS BASED ON INVERTED FILES

Table 2-1
Terms
APPLE
ORANGEBANANA
GRAPE

27

Sample Inverted Index
Document reference
numbers
1 3 5 72 3 4 5 6

4 6 8
3 7 9 11

the right, the items to be retrieved are identified by the document reference
numbers
3 4

5 6 8

because the set intersection between the sets for APPLE and for ORANGE
produces items 3 and 5 to which are added items 4, 6 and 8 when the set union iscarried out with the BANANA set. On the other hand, if one starts at the rightand works toward the left of the query statement, then the items to be retrieved
are given by the document reference numbers
3 5
because the union between ORANGE and BANANA produces items 2, 3,4, 5,
6, and 8 and the intersection that follows with the set for APPLE restricts theoutput to 3 and 5.
The order in which the operations are carried out is critical. The strategy
may be left-to-right or right-to-left, or some other method may be used to spec­
ify the order in which the operations are to be executed. For instance, one pro­cedure specifies that all the OR operators are performed first, followed by the
AND operators, and finally the NOT operators; all equivalent operators are
performed from left to right. Parentheses are usually provided to circumventthe strict processing order described above. In particular, operations within pa­
rentheses are normally completed first. For the previously used example theleft-to-right order is thus equivalent to (APPLE AND ORANGE) OR BA­
NANA, whereas the right-to-left order corresponds to APPLE AND (OR­ANGE OR BANANA). Each operation or set of operations within parentheses
is first carried out according to the regular processing rules. When this is com­pleted, the remainder of the query statement is processed. Consider the query
statement:(APPLE AND ORANGE) OR (BANANA AND ORANGE)The following process may be used for this statement:
1
The first AND operator on the left side of the query statement com­bines the document reference numbers associated with APPLE and ORANGE(items 3 and 5).

26

CHAPTER 2

2 The second AND operator combines the document reference numbers
associated with BANANA and ORANGE (items 4 and 6).
3 Finally the OR operator combines the sets retrieved in steps 1 and 2(items 3, 4, 5, and 6).
The set of documents retrieved by using the parentheses differs from the sets
retrieved by rules given earlier. Once the rule for parentheses has been estab­lished, it can be applied over and over again. That is, nested parentheses can beused so that the operations within the innermost pair of parentheses will be car­ried out first. For instance the query statement(APPLE AND (ORANGE OR BANANA)) NOT GRAPE
is executed beginning with the (ORANGE OR BANANA) portion of the query
statement. In order to allow parentheses, it is necessary to keep track of inter­mediate results. For this reason, some systems do not allow the use of paren­theses and others allow only limited nesting of parentheses.

2 ADJACENCY AND TERM FREQUENCY FEATURES

Each commercial system includes certain features that make it unique. This
complicates the problem of learning how to use each of the systems. A few ofthe more interesting and basic operations are described in the remainder of thischapter. Since the various processing approaches are considered to be proprie­
tary information by the system vendors, there is no assurance that the methods
presented here are strictly factual. The presentation of the basic methodologies
covered in the next few paragraphs is, however, expected to be reasonably ac­
curate.
A

Adjacency Operations

Consider a retrieval system which allows the searcher to formulate queries
using words included in the document texts. It may be useful to specify that
two words must appear next to each other in a text and in the proper word
order. If the operator ADJ stands for adjacency, a query for documents on “in­formation retrieval’’ may now be stated as
INFORMATION ADJ RETRIEVALThe searcher is then assured that the two search terms do not appear in unre­
lated portions of the document but are in fact contained in adjacent word posi­tions.Thus, the probability that the concept “ information retrieval” is con­tained in the document is higher than if the searcher were to use the terms
INFORMATION and RETRIEVAL combined by an AND operator.
It is difficult to implement the adjacency operation using the basic defini-SYSTEMS BASED ON INVERTED FILES

29

tion of the inverted file. The following procedure may be used, however, when
only a basic inverted index is available:
1 Use the standard inverted file to identify the documents that satisfy thequery
INFORMATION AND RETRIEVAL
2 Use the document file to search specific fields of the corresponding
documents by means of a character by character match (a string search) to de­tect the presence of the characters “INFORMATION RETRIEVAL.” The
fields to be searched are normally prespecified and may include the title andabstract for each document.
3 Retrieve from the document file those items for which at least one com­plete match of the given character string is found.
String searching is a laborious task which consists in scanning an arbitrary setof symbols in search of a specific sequence of symbols. That is, the text of adocument is examined character by character until the desired sequence ofcharacters is found. String searching procedures are implemented in certain
systems but are used only when essential. In particular, the system normallywarns the user of the inefficiency of the string searching process, and various
restrictions may limit the conditions under which string searching may be con­ducted.
Another possibility for implementing the ADJ operator consists in enhanc­
ing the inverted file by adding information about the location of words withineach document. For instance, if the stored documents consist of abstracts of
two or more paragraphs, and each paragraph includes several sentences, then
the term location information might include the document reference number,paragraph number, sentence number, and word number within each sentence.
Thus, RETRIEVAL (345 1 2 5) would indicate that the term RETRIEVAL
occurs in the first paragraph, second sentence, and fifth word of document 345.
Document 345 would be retrieved by the query statement
INFORMATION ADJ RETRIEVAL
whenever the entry INFORMATION (345 1 2 4) appears in the inverted file inaddition to the entry RETRIEVAL (345 1 2 5).
Another way to provide term location information is to add to each term
entry in the inverted file a distance indicator specifying for each word occur­
rence the distance from the beginning of the text in terms of the number of in­tervening words. Thus, RETRIEVAL (345 13) indicates that the term RE­
TRIEVAL occurs 13 words from the beginning of document 345. Again
document 345 would be retrieved by the previous query only if INFORMA­
TION (345 12) were also included in the enhanced inverted file. This proceduredoes not recognize sentence boundaries and is not therefore completely equiva-

30

CHAPTER 2

lent to the previous method based on paragraph, sentence and word numbers.
In practice, the two methods are probably equivalent in terms of retrieval per­formance.
A comparison of the methods for carrying out the ADJ operation showsthat the character by character analysis of documents requires substantial com­putational resources but the inverted file is not encumbered with additional
word location information. The other two methods are based on an expanded
inverted file. When word location information is kept in the inverted file, little
extra processing is required for the ADJ operation with the exception of anadded comparison between two groups of numbers to determine the appropri­ate order. The added word location information does, however, take up a great
deal of potentially valuable storage space.
To date the tradeoff has seemed clear. The character by character search­ing, as usually implemented, is so inefficient that the use of extra storage in the
inverted file appears mandatory. However, fast string searching operations
have recently been discovered that may reverse this situation. These methods
will be discussed in Chapter 8 of this volume.
B

Frequency Information

Another way of enhancing an inverted file system is to include information
about the frequency of occurrence of the individual terms. It has been shownthat special usage patterns exist for the words included in natural language
texts in certain subject specialties. In particular, the frequency of use of a given
term may correlate with some indication of the importance of that term in thegiven subject area. If word frequency information is to be used in retrieval, it
must be stored by the system, and the most practical way to do this is to include
the information in the inverted file. In many systems “posting”information is
kept in the inverted file for each term. That is, the inverted file includes infor­
mation about the number of documents in which a given term occurs. This fre­quency information is referred to as the number of postings for the term. In thisway a user can quickly ascertain the number of documents that will be re­trieved by using a given term. For instance, the term INFORMATION has
53,504 postings in the ERIC data base available through the DIALOG system atthe time this is being written. A query which includes only this single term
would therefore retrieve 53,504 documents.
3 COMMERCIAL INVERTED FILE SYSTEMSAThe DIALOG System

The DIALOG system is a product of Lockheed Information Systems of Palo
Alto, California. In May of 1980 some 122 individual data bases were available
through the DIALOG system [6,7].
The DIALOG system is based on an inverted file design. The system cre­ates sets of document reference numbers by means of a SELECT command.

SYSTEMS BASED ON INVERTED FILES

31

Thus, the SELECT INFORMATION command creates a set of document ref­erence numbers associated with the term INFORMATION. The system pro­vides the user with a set number identifying these document reference num­bers. For example, the statement given earlier would be assigned set number 1
if it were the first SELECT command issued by the searcher. A second com­mand SELECT RETRIEVAL would therefore create set number 2. These sets
may then be processed by a COMBINE statement which allows the use of theBoolean operators AND (*), OR (+), or NOT (-). Thus the statements
COMBINE 1 AND 2
or
COMBINE 1 * 2
are used to form the query statement
INFORMATION AND RETRIEVALThis query was introduced earlier in this chapter when the document reference
numbers associated with INFORMATION (Set 1) and the reference numbers
associated with RETRIEVAL (Set 2) were combined with an AND operator toform the new Set 3. The NOT operations are performed first in the DIALOG
system, followed by the AND operations, and finally by the OR operations. Pa­
rentheses are allowed in order to alter this specified sequence of operations.
Thus, a statement such as
COMBINE (4 OR 5 OR 6) AND (7 OR 8) NOT 9
produces a legitimate search operation assuming that Sets 4, 5, 6, 7, 8, and ;9have all been previously defined.
In the DIALOG system a term may be truncated on the right to indicatethat any characters following the truncation symbol are acceptable. For exam­
ple, PSYCH? can be used as a search term to retrieve items associated withPSYCHIATRISTPSYCHIATRY
PSYCHOLOGICALPSYCHOLOGISTPSYCHOLOGY
and any other terms that begin with the characters PSYCH. The truncation
symbol “ ?” may also be used to specify the maximum number of charactersthat may appear following the user supplied characters. The number of charac-

32

CHAPTER 2

ters allowed is indicated by the number of “ ?” symbols immediately after theword followed by a blank and another “ ?” symbol. For example,
DOCUMENT??

?

specifies that the search term DOCUMENT may be followed by up to 2 addi­
tional arbitrary characters. Thus, documents associated with the terms DOCU­
MENTS and DOCUMENTED will be retrieved, but documents associatedwith the term DOCUMENTATION will be rejected.
The truncation operations can be carried out in an obvious manner using
an inverted file. In the first case (truncation without limits), the inverted fileneed only be searched for the terms whose initial characters correspond to theuser input. Using the PSYCH? example, the system need only examine the first
five characters of the terms included in the index file. If an exact match isfound, the associated document reference numbers are placed in the retrieval
set. The same logic is used for truncations with a limited number of trailingcharacters. That is, an exact match of characters is required between the char­acters supplied by the searcher and the characters of the term stored in theindex file. Once this condition is satisfied, it is necessary to consult the index
file to determine if the number of additional characters of the given term in theindex file meets the criterion specified by the user. In order to determine thatthe matching term carries the right number of trailing characters, the characters
specified by the ? symbols need not be examined individually. However, char­acters occurring to the right of those specified by the ? symbols must be consid­
ered. If no characters occur in the term stored in the index file beyond the last ?
symbol, the corresponding document reference numbers are retrieved.
The truncation character “ ?” may also be embedded inside a term sup­plied by the user. For example, WOM?N would be used to indicate both theterm WOMAN and the term WOMEN. The process used to handle requests ofthis kind may be based on methods similar to those described earlier. Note that
there is no need to add any location or frequency information to the inverted
file.
DIALOG also offers the ability to search for pairs of adjacent words or forterms occurring within a specified number of words of another term. This capa­
bility is based on the use of terms derived from the actual texts of documents or
document abstracts, as opposed to terms assigned from a controlled vocabu­
lary. Controlled terms are not generally assigned in any meaningful sequence.
The pertinent operator used is “ (W),” and it must be used with the SELECT
operator. Thus,
SELECT PROGRAMMING (W) LANGUAGE
would retrieve the documents from a data base which included the terms PRO­GRAMMING and LANGUAGE occurring side by side in the text and in thatstated word order. As in the case of the ADJ operator discussed earlier, theSYSTEMS BASED ON INVERTED FILES

33

corresponding search can be carried out either by processing the actual texts of
documents following identification of items which include both terms, or byadding location information to the inverted file. In the DIALOG system, theinverted file is enhanced by the position number of each word within each doc­
ument. Thus retrieval is based on the determination of consecutive word posi­tion numbers in the inverted file.
When word position information is available, one can also determine if two
particular terms occur within a specified number of words of each other in a
text. This is done by subtracting the location number of the first term from thatof the second one. If the order of occurrence of the terms is deemed important,
one may want to insist on a positive difference between location numbers. If
the difference is allowed to be either positive or negative, the order of the terms
is disregarded. Thus,
SELECT PROGRAMMING (5 W) LANGUAGE
would find all documents in which the term LANGUAGE follows the term
PROGRAMMING within a distance of up to five words; term order is clearlytaken into account. If term order is not important, the term LANGUAGE may
either precede the term PROGRAMMING by up to five words, or it may follow
PROGRAMMING by up to five words. In the DIALOG system the order of thewords is important and the system assumes they are to appear in the orderspecified in the query statement.
The DIALOG system also uses field identification for author (AU), classi­
fication code (CC), corporate source (CS), document type (DT), journal name
(JN), language (LA), publication year (PY), and update (UD). The latter fieldindicates when the document was added to the data base. Since some of thesefields contain measurable values, it is possible to include the corresponding
values in a search statement. For instance, a range of values can be specified
for the publication year as follows:
SELECT PY = 1977 : PY = 1979
which indicates that documents with a publication year between 1977 and 1979
are acceptable. The colon (:) designates a range of measurable values to be
used.
From a computational point of view such a process seems to present prob­
lems. If the publication year is included in the inverted file for each document,
then in order to select the appropriate range of publication years one mustsearch for exact matches corresponding to the whole range of allowable publi­
cation years or be able arithmetically to compare the publication year. Thus,
for the example given earlier the specified dates must include 1977, 1978, and1979. The number of possible representations for a publication date in a given
data base is quite large. For example, 1978, June 1978, 6/78, and ’78 may all be
used to represent publication dates for the year 1978. If all those alternatives

34

CHAPTER 2

were allowed in a retrieval system, a complicated search would become neces­sary. In the DIALOG system a specific representation is selected, in this exam­ple 1978. This makes it possible to carry out exact matches on specific dates toretrieve documents with date specifications. Alternatively, it is quite feasible tokeep a separate inverted index for publication dates alone. Assuming that sucha file is kept in chronological order and in a numeric representation, the systemneed only search for values in the range 1977:1979. Thus, a document may
have terms,or values assigned from a number of different inverted indexes. A
different index may be used for each field of the document such as publication
year or author. Different indexes may also help to distinguish identical values
for different keys such as publication year 1980 and page number 1980.
Many other features are included in the DIALOG system. In this discus­
sion some of the important features have been highlighted to indicate ap­
proaches that have been used by the system designers.
*B

The STAIRS System

Another prominent system is the storage and information retrieval system(STAIRS), which is a program product of the IBM Corporation. Whereas the
STAIRS system itself is available through IBM, no data bases are made avail­able by IBM. Rather the user must purchase or lease the STAIRS programs andapply the system either to commercially available data bases or to private databases. STAIRS runs on the customer’s own computer.
STAIRS consists of two sets of programs:
1 Utility programs for data base creation and maintenance
2 An on-line retrieval system called AQUARIUS, which stands for aquery and retrieval interactive utility system.
The retrieval function is a multiuser system which develops an effective dia­logue with the user. This dialogue leads to the search and eventual retrieval ofstored data.
A principal difference between STAIRS and DIALOG is that a full
STAIRS implementation includes not only a text processing and document re­trieval function but also an associated data base management system. The
latter is designed to process formatted (highly structured) information such as
numeric data available in tabular format. In the data management context, theretrieval of records is based on the values of particular attributes of the records.
STAIRS uses separate modes of operation to handle text and structured data
known as the SEARCH and SELECT modes, respectively.
To use the text retrieval system it is necessary to create an inverted file, atext index, and one or more text files. These are illustrated in Fig. 2-1. The text
file contains the documents using a special format in which the retrieved docu­
ments are presented to the retrieval system users. The text index includes
pointers to records in the text file, as well as privacy information and formatted
data associated with subsets of records in the text .file. These formatted data

■E^
*1
= sw

5-S

sE

St

,CL

CJ

f.

e 0
u»
>
C£
o .5
5. a
to

...r s jm w i
Dictionary

Inverted
file
pointer■oaf -;!*j
'jM'

5

C
<D
E ~o
3 ra
U
0
o JS)
Q

g

,

E,S

■0's i■§o

STAIRS file organization. (Adapted from reference 8.)

*e
E■
oS E
.5?

E-g

§■§
2 c

Figure 2-1■gsC O gt

35

36

CHAPTER 2

include attributes for which a range of values can be specified in advance. Be­
cause the allowable values are known in advance, the manner in which thevalues appear in the files can be prespecified. For instance, the publication
dates may be restricted to the format “ 1978” and dates of the form 6/78 or any
other format will be disallowed.
The dictionary contains a record for every unique word included in thedata base. Associated with this entry is a pointer to a list identifying each oc­
currence of the particular word in the text. This is of course the inverted index
described earlier in this chapter. The inverted file portion of the system may
also be used to identify words which are synonymous with a given term. The
system accomplishes this by maintaining a separate synonym dictionary. Ac­
cess to an individual word in the dictionary is obtained by using letter pairs.
That is, the first two letters of any word are used to identify a specific groupingof terms which is searched in order to find the wanted term. Associated withthe term is a pointer to the list of associated document reference numbers. The
dictionary has two levels: the first level contains the information about theletter pairs and indicates where the search must start on the second level to findthe words beginning with particular letter pairs; the second level contains theactual words along with associated word length information and synonym in­formation. Thus the dictionary itself is organized as an indexed file (see Fig.
2-2). Note that the location information in the inverted file consists of threenumbers (triplets) representing paragraph code, sentence number, and word
number. This information is present for each occurrence of each word in thedata base.
The STAIRS retrieval system uses the free text of the documents or docu­
ment abstracts for search purposes. The location information for each term is
an important part of the STAIRS system, as is much of the remaining informa­tion described in Fig. 2-1. Controlled vocabulary terms may also be used with

Dictionary*

HeaderPointertoletterpair 1

Pointertoletterpair 2

Letterpair 1
control
inform ation

Word entry
lengthinform ation

Word
1

Word
2

Inverted
file
pointer

Synonympointer

Word

Pointertoletterpair 1406

T .

-Figure 2-2 STAIRS dictionary organization. (Adapted from reference 8.)

SYSTEMS BASED ON INVERTED FILES

37

the STAIRS system. In that case the location information is not helpful, since
the controlled terms are never combined using adjacency or term distance mea­sures.
Documents are found in STAIRS using the SEARCH command. When
this command is specified, the SEARCH mode is entered. In this mode the user
searches the unformatted portions of the records. Each search statement, nor­mally consisting of a term followed by an operator and another term, is as­
signed a number of the STAIRS system. For example,
HEART AND DISEASE
is a legitimate search statement in which the normal Boolean AND operator isused. Other legitimate search statements include
HEART
HEART OR DISEASE
HEART NOT DISEASE
HEARTS AND DISEASE$3(HEART OR CORONARY) AND DISEASE
The “ $” symbol indicates truncation and the “ $3” indicates truncation with up
to three unspecified characters. Other operators of interest are
ADJ
specifying that two terms must be adjacent to one another,
WITH
indicating that the two terms must appear in the same sentence,
SAME
specifying that the two terms must appear in the same paragraph, andSYN
specifying that the two terms are to be considered as synonyms. The use of
these operators is based on a straightforward manipulation of the files pre­sented in Fig. 2-1. Adjacency (ADJ), same sentence (WITH), and same para­graph (SAME) operations use the available location information to ensure thatthe necessary retrieval criteria have been met. For example, a search statement
such asPROGRAMMING WITH LANGUAGE
specifies that the two terms must appear in the same sentence.

38

CHAPTER 2

The synonym dictionary is developed by recognizing term equivalences
specified by a SYN command. Thus two terms are considered as synonymous
when they are connected by the SYN operator. If COMPUTER and MA­
CHINE are both entries in the existing dictionary,
COMPUTER SYN MACHINE
means that the user needs to specify only one of the terms to formulate a querycovering either term. Note that a place is left in the dictionary for the synonym
pointers. The SYN operation can easily be implemented by placing in the syn­onym pointer location of each component of a synonymous pair the location of
the other component. A query which specifies COMPUTER as a term would
then automatically also refer to (be pointed to) the term MACHINE. Document
reference numbers for both terms would be retrieved using either term in aquery.
The following hierarchy of operations is used to process the STAIRS state­ments:ADJ
SYN
WITH
AND, NOT
OR, XORwith the ADJ performed first, and OR or XOR (exclusive OR) operations per­formed last. The XOR operator indicates that a document is selected wheneverit contains either of the specified terms but not both. Parentheses are allowed inorder to alter the order in which the operations are performed.
The DIALOG and STAIRS operations appear reasonably similar eventhough the commands actually used are named differently and the underlying
file structures.differ in many details.
To manipulate structured data, the STAIRS system uses the completely
separate SELECT mode of operation. In that mode the formatted fields of datanormally containing the values of record attributes are searchable. The SE­
LECT mode provides new search operators and operates on portions of the
documents different from those specified earlier for the SEARCH mode. For
instance, a special AND operation is provided which acts across several dis­tinct formatted fields (major AND); another AND operator is used to operate
within a given field. The same is true for the OR operator. For example, thequery
SEX EQ MALE AND HAIR EQ (BROWN OR BLOND)
selects records for which the HAIR field is specified as BROWN or BLOND
and at the same time the SEX field equals MALE.

SYSTEMS BASED ON INVERTED FILES

39

In the SELECT mode special relational operators may be used in a query
statement in addition to the standard search operators. These relational opera­
tors specify restrictions on the values of certain attributes attached to the docu­
ments. For instance, one may wish to retrieve all items described by an attrib­
ute called AGE with a value for AGE greater than 30; alternatively all items
may be wanted with an attribute called SEX equal to FEMALE. In the SE­
LECT mode each attribute is given a name and the attributes are characterizedby particular values in each given document. In other words, a given attribute
called AGE may be defined in the data base and the value associated with that
attribute may be set equal to 25 in a specific document. A query statement used
to retrieve this document might specify
AGE EQ 25
where EQ represents an operator specifying equality. Other relational opera­
tions include not equal (NE), not greater than (NG), not less than (NL), greaterthan (GT), less than (LT), within limits (WL), and outside limits (OL). A query
statement such as
SEX EQ MALE AND AGE WL 25 , 35
specifies that the items to be retrieved must have attributes called SEX and
AGE, the value of the SEX attribute being equal to “MALE,” and the value ofthe AGE attribute lying within the specified limits of 25 to 35. As in the
SEARCH mode, the system assigns numbers to the individual query state­ments.
Although the search operators may not be mixed between the SELECT
and the SEARCH modes, one can use a query number from the SELECT mode
as a part of a query statement in the SEARCH mode. Thus, if the earlier query
including the attributes SEX and AGE is assigned query statement number 1 by
the system, then the corresponding set of document reference numbers can be
combined with other sets based on the specification of words in the SEARCH
mode. For example, in the SEARCH mode one might use a query statement
such asI

AND INFORMATION ADJ SPECIALIST.

to indicate that the items to be retrieved must have all the following properties:
1 The formatted attribute SEX must be equal to “MALE.”
2 The formatted attribute AGE must have a value within the limits of 25
and 35.
3 The term INFORMATION must appear in the item.
4 The term SPECIALIST must appear in the item.
5 The term INFORMATION must immediately precede the term SPE­CIALIST in the item.

40

CHAPTER 2

Note that the adjacency operator (INFORMATION ADJ SPECIALIST) isevaluated before the AND operator in accordance with the precedence pre­viously established.
The processing of information in the SELECT mode differs from the typi­
cal information retrieval processing. Rather it fits into a framework explicitly
used to handle structured information. The IMS (Information Management Sys­tem) data base management system is often associated with the STAIRS re­trieval system to carry out the structured data manipulations. IMS uses in­verted file structures in the sense that for each value of each allowable attributea list of associated document reference numbers is stored by the system. Pro­
cessing of the AND and OR operators is therefore a matter of set intersection
and set union as previously described. To handle the remaining operators suchas “greater than” and “less than” it is necessary to determine if the specified
attribute values meet the desired relational criterion.
Another feature of STAIRS is its ability to rank the retrieved documents
according to one of several prespecified algorithms. The RANK command isused to operate in a special ranking mode. In the RANK mode the initial searchis carried out using the SEARCH mode of operations previously described—
sets developed in the SELECT mode are not available in the RANK mode.
Once a document set has been chosen for retrieval using the SEARCH mode
operations, a ranking of the documents can be obtained by assigning values orweights to the individual terms associated with a document. The retrieved doc­
uments may then be presented to the user in ranked order according to the sumof the weights of all terms that match the terms included in the user’s query.
The value of a term associated with a document is determined by a user se­lected combination of:
1 The frequency of the term in the document
2 The frequency of the term in the retrieved set
3 The number of documents in the retrieved set in which the term occurs
One particular term weighting algorithm uses the following formula:frequency of
frequency of
the term inx the term in,„
the document
the retrieved set
Value of term = ------:------ -------------- -—:-----—:------ number of documents in retrieved
set containing the term
Consider, for example, a term such as SALINE which appears in 152 dis­tinct documents retrieved by a particular query for a total of 1,247 times in all.
Assuming that this term occurs 16 times in a particular document, the value ofthe term SALINE for this document is then determined as
Value of term =16 x 1,247
152

131.26

SYSTEMS BASED ON INVERTED FILES

41

A final value can be calculated for each document by summing the values of allterms which match the query terms. In the RANK mode, documents are pre­sented to the user in decreasing order of the term value function, the assump­tion being that this order corresponds to a decreasing order of presumed rele­vance of the documents with respect to the corresponding query.
STAIRS is a uniquely powerful system. It is designed to offer a great dealof flexibility in the sense that it offers all the power of a free text search system
in addition to the formatted retrieval capability based on the values of specificattribute fields. However, the STAIRS system may be expensive to use in thatit requires a data base management system in addition to the retrieval system,
as well as a large storage capability for the term location, frequency, synonym,
and associated information. Furthermore, the user must have a large IBM com­puter system available for use.
C The Bibliographic Retrieval Services (BRS) System

The Bibliographic Retrieval Services (BRS) system is a system that uses
STAIRS as a basis [9]. BRS is a commercially available system operating on
about forty data bases. The system had its origins in the biomedical communi­
cations network of the State University of New York.
BRS operates exclusively as an information retrieval system and not as adata base management system. Thus, many of the commands included in
STAIRS are eliminated. Since no data base management facility is available tothe user, there is no need to distinguish between, the SELECT and the
SEARCH modes. The user may use a LIMIT operator, however, to specify
values such as publication year or language. In addition the ranking ability is
not present in BRS. Hence the RANK mode has also been deleted. The one
remaining mode of operation, the SEARCH mode requires no special identifi­
cation. The operations used are those included in the STAIRS SEARCH modewith certain added features. One specific extension allows the qualification of asearch statement after the search has already been conducted. Thus, one can
supply special field designations in the query statements that limit the output
produced by an earlier search. For instance, the code TI refers to the title fieldof a document. A search statement such as
1: PROGRAMMING ADJ LANG$
first identifies all documents containing the term PROGRAMMING adjacent toterms which begin with the characters LANG (such as LANGUAGE or LAN­GUAGES). The nuihber 1: designates the query number. The initial searchstatement can be modified by specifying
2: l.TI.
which implies that search statement 1 is to be modified to restrict the two
search terms to the title field only. If a document includes the terms in adjacent42

CHAPTER 2

positions in the abstract of the document but not in the title, then that document
will not be retrieved.
An advantage that BRS maintains over the STAIRS system is its simplicity
and processing efficiency. The removal of many of the commands, modes, andfunctional requirements available in STAIRS produces a much cleaner andsimpler processing framework. Fewer decisions must be made and simpler pro­grams are used. Furthermore, users do not need either their own computer ortheir own data bases, and the system is easier to learn to use than STAIRS. The
designers of BRS have thus identified the most used portions of STAIRS andconfined their attention to the implementation of a streamlined information re­trieval system.
D The MEDLARS System

Perhaps the most famous of all available information retrieval systems is the
MEDLARS system of the National Library of Medicine (NLM). This system
was built as a result of activities initiated in 1964 aimed at the publication of an
automated form of Index Medicus. Experiments with on-line bibliographic re­trieval systems began in 1967. The first system used the Abridged Index Med­icus (AIM) as a data base that became accessible through the Teletypewriter
Exchange Network (TWX). AIM-TWX proved the viability of an on-line infor­
mation retrieval system.
Following the construction of the early system NLM in cooperation with
the System Development Corporation (SDC) modified the on-line retrieval of
bibliographic information— timeshared (ORBIT) system to meet the special
needs of NLM. MEDLARS first appeared in 1971, and several revisions havesince been made both to the data base structure (MEDLARS) and to the on-line
search package (ELHILL). The number of available data bases has increased
and the capabilities of the system have been enhanced [10-12]. Unlike theother systems previously mentioned, the coverage of MEDLARS is largely re­stricted to documents in the biomedical area.
The structure of the MEDLARS system is principally based on the use of
inverted files. Three different files actually constitute this system: the INDEX
file, the POSTINGS file, and the DATA file. The data file stores the complete
information associated with each record; this includes all the data which can bedisplayed for the user. Each record is identified by a unique reference number,in this case called the computer assigned number (CAN).
The index file contains all the unique search terms, such as author names,
terms from a controlled vocabulary, numbers such as dates, and classification
codes. Each entry in the index specifies the term and the document field inwhich it may be found. For instance, JONES (AU) specifies that the term
JONES is located in the author field of the document. Following this informa­tion, a two-part number is recorded in the index. The first portion of this num­
ber is a reference to the postings file. That is, it designates the position in thepostings file where information about this term begins. The second portion of
the number specifies the number of postings associated with this term. Table

43

SYSTEMS BASED ON INVERTED FILES

Table 2-2 MEDLARS Inverted Index
Organization

Search term

Sequence
numberaddress

Postings

ABDOMEN (MH)AGED (MH)AGEE JW (AU)

527
1073
1075

3213
51604
4

ZYMOSAN (MH)

10379

62

Adapted from reference 11.

2-2 shows the organization of the index file. The term ABDOMEN occurs in themain heading (MH) field of the given document, information about the term
begins at location 527 in the postings file, and 3,213 different postings are asso­
ciated with the term. The postings file contains the CAN numbers which iden­
tify the specific documents associated with each term. Associated with the term
ABDOMEN, 3,213 distinct CAN numbers are therefore listed beginning at lo­
cation 527. Figure 2-3 describes the overall structure of the MEDLARS systemand the path of a query through the various modules of the system.
The commands used by the MEDLARS system are similar to those de­scribed earlier for the DIALOG and BRS systems. The format differs in that nosearch mode is selected by the user and no parentheses are allowed. The user
must adhere strictly to a hierarchy which requires that all AND operations are
performed prior to any OR operation. Thus if a user is interested in “computer
languages” or “programming languages” then
1: COMPUTER OR PROGRAMMING AND LANGUAGE
will not produce the desired result. Rather, the two statements
1: COMPUTER OR PROGRAMMING
2:1 AND LANGUAGE
are necessary.
The user is allowed to conduct a string search within MEDLARS. A pre­liminary search is first conducted and the retrieved set of documents is thenscanned to find a specific string of characters in the texts. Thus, a given set of
documents can be examined on a letter-by-letter basis in the hope of detecting agiven word or phrase occurrence. For instance, the command
STRINGSEARCH 1: HEART DI:
can be used to find those records identified as a result of a previously definedHeader file</)
H- C -*0 0) Q)55 g|>23 8Q)£ is|ms toicz S- 5

Postings file<£ a
HI 2 <D
—
i<
5 s.
2
m
<
.
«- ra
O"O
§c »o S®
«<5£ £"S)^ <i>_ c cm nf ®o(5a**» t) £” C 0)< « .t;C CM —■ s j§

CO CM A)
CO -C
C 1—

CO </) (0g)Q) w

CO

CM

o wco
a) £ cWc |:— «+— Q)

I Baker (AU) 1

1
1 Able■Index file

1
O1
o

§s§
—J +- "0H
I <J>.2^ E to
^ 3.2
Oxc>
COO
(U^S
3 C

73

•2
Li.>2® $3

44

SYSTEMS BASED ON INVERTED FILES

45

search statement 1 which exactly match the string of characters HEART DI.
The user may then be increasingly confident that the search results are indeed
related to the concept of heart disease. Note that the query HEART AND DIS­EASE may well retrieve items that have nothing directly to do with heart dis­ease, such as, for example, items dealing with the effects of lung disease on theheart. On the other hand, documents containing the terms “HEART DIMEN­SIONS” will also satisfy the sample string search.
A string search may be expensive to perform when conducted by mostavailable algorithms. The MEDLARS system therefore limits the potential costby restricting the string search to document sets retrieved by earlier searches,and by allocating limited time slices for the string search operation. At the endof a given time slice, the system informs the user of the number of documents
found so far containing the requested character string. The user is then asked toapprove the continuation of the string search process. The same procedure isfollowed at the end of every time slice. The user may be quickly discouraged by
the repetitive procedure. In fact, most sophisticated users limit string searches
to small sets of documents.
The efficiency and effectiveness of the MEDLARS system have been re­peatedly evaluated. Because the system constitutes the first international on­
line information retrieval system it enjoys a worldwide reputation. There will
be further occasions to refer to this system later in this text.
E The ORBIT System,

The ORBIT system provided the basic foundation for the design of MEDLARS.
It should not be surprising that the two systems exhibit many common features.
The basic operational environment is common in both systems. The existing
differences are related to the specific procedures designed to help the user inthe search process. For instance ORBIT allows the user to generate a chrono­
logical display of various search statements entered by the user during thesearch effort. MEDLARS does not include such a feature. Both MEDLARSand ORBIT do, however, allow the user to view a hierarchical diagram of thesearch logic [13,14],
F The Information BankThe Information Bank provides access to the news articles and editorials pub­lished in The New York Times, and to additional articles from numerous other'publications. The search vocabulary is strictly controlled, and the logical oper­
ators AND, OR, and NOT are used to relate the terms included in a searchstatement. Terms entered by a user for which an entry is not found in the term
index initiate a dialogue between system and user. The user is eventually asked
to select terms from a displayed list of available terms. Searches may be re­stricted by specifying fields such as date or type of material. The output may besorted chronologically.
The Information Bank is powerful because the available data base consti­
tutes a unique source of newspaper materials which is not otherwise easily ac-

46

CHAPTER 2

cessible. Plans are under way, however, to render the data base of the Informa­tion Bank also accessible through the BRS system. The Information Bank may
be particularly valuable to public figures, university professors, students, andin fact to anybody concerned with current or past public events. The Informa­tion Bank significantly contributes to the current popularity of on-line informa­tion retrieval systems. On the other hand, the technical design features of thesystem are essentially the same as those of the other systems discussed earlier[15,16,17],
G The LEXIS System

The LEXIS system offered by Mead Data Central provides a service specifi­
cally devoted to the manipulation of legal information. The documents are in­dexed automatically from the text of the items which is stored in its entirety inthe system. The searcher uses the traditional Boolean logic to connect the text
words included in the search statements. In addition, word location informa­tion may be used by insisting that terms appear in a specific portion of a docu­
ment, within a specified number of words of one another, and in a particularword order. The search terms consist of text words assumed to have a specificmeaning related to the document content. Common words such as “the,” “it,”and “her” are excluded. The common terms are deleted at the time the docu­
ment is first entered into the system and are not processed any further or en­
tered in the inverted file. Hyphenated words such as ANTI-TRUST are used as
two separate terms in the LEXIS system. Thus, the term DATA-BASE isstored as two entries under DATA and BASE, and is considered distinct fromDATABASE. Some special word endings can be recognized by LEXIS and re­duced to common forms; for example, the terms CITY, CITIES, CITY’S, and
CITIES’ all retrieve the same document set. Complex morphological differ­ences such as CHILD and its plural CHILDREN are not, however, recognizedas equivalent terms.
The processing of terms necessary to remove common words and to iso­late terms with common word stems occurs prior to the use of the inverted file.
Thus, the LEXIS input processing is distinctly different from the document
input and analysis methods used by the other systems described so far. No
other publicly available system stores the full text of all documents and uses it
for search and retrieval on the scale of LEXIS. Following the elimination ofcommon words and the generation of word stems, LEXIS uses an inverted filesystem similar to those included in the other retrieval systems. The inverted fileretains word location information which may be used either with or without
specified word order information. In this sense, the LEXIS system performs
much like DIALOG or STAIRS [18].
4

ENHANCEMENTS OF BASIC RETRIEVAL STRATEGYThe use of an inverted file structure appears to be a prominent feature of theexisting commercial information retrieval systems. The main inverted file con-

SYSTEMS BASED ON INVERTED FILES

47

cepts appear to have been used initially on a computing device by Herman Hol­
lerith, who introduced punched cards to handle the computational work for the1890 United States Census. Since that time the basic inverted file design has notbeen radically modified. New term location and term frequency information
has been added, as in the STAIRS, DIALOG, and LEXIS systems. But the fileorganization using individual terms and document reference numbers has re­mained unchanged. This organization can easily handle Boolean operators bytranslating the AND, OR, and NOT operations into the set intersection, setunion, and set difference, respectively. Thus, inverted file procedures are easy
to implement and offer the user a powerful way of expressing informationneeds.
The use of unweighted term combinations such as
ALPHA AND BETA
implies that the user considers the terms ALPHA and BETA equally impor­tant. If these terms are not equally important, some means is required to ex­press term importance. Typically the searcher is asked to specify term impor­tance by assigning numeric values to terms. For instance, values between 1 and10 could be used to designate terms of little importance (1) as well as terms of
most importance (10). The user may also be asked to specify a threshold to de­termine which documents are to be retrieved and which are to be rejected.
Thus, given the weights and thresholds
ALPHA = 4
BETA = 5
GAMMA = 6
Threshold - 10
a query such as
ALPHA OR BETA OR GAMMA
would retrieve the following document sets in order:
1 Documents containing terms ALPHA and BETA and GAMMA (4 +5 + 6 > 10)
2 Documents containing the terms BETA and GAMMA (5 + 6 > 10)
3 Documents containing the terms ALPHA and GAMMA (4 + 6 > 10)
This assumes that the terms occurring in the documents are unweighted andthat satisfactory methods are available for choosing appropriate weights for thequery terms.
The query term weights produce a partial ranking of the retrieved docu­
ments which may improve user satisfaction. However, in practical situations

48

CHAPTER 2

term weighting has not produced substantial improvements in search satisfac­
tion. The reason seems to be that a great deal of effort is required on the part ofthe searcher to determine correct weights and assign them to the various terms.
Thus, de facto, most searches are conducted using the basic inverted file sys­
tem organizations with unweighted terms.
The inverted file process permits a great deal of flexibility in the design of
the user-system interfaces. Even though most systems are based on the same
fundamental file organization and search strategy, different ways exist for pre­senting the information to the user. The manner in which commands are pre­sented, the hierarchy of operations, and the different operators allowed in eachsystem render each system unique.
Currently, several hundred data bases are associated with the various sys­tems. These data bases include millions of documents. Thus, an enormous in­vestment exists in systems designed to operate with inverted files. The intro­
duction of changes and modifications to the existing commercial retrieval
systems must therefore depend upon not only the technical feasibility but also
the economic impact of the alterations. The great expansion in the availability
and use of retrieval systems over the last dozen years leads one to expect acontinued growth in system development and services in the years to come.
REFERENCES[1] D . F ife, K. Rankin, E. F en g, J. W alder, and B. Marron, A T echnical Index o f Inter­
active Information S y stem s, S ystem s and Softw are D ivision , Institute for C om ­puter S cien ce and T echnology, N ational Bureau o f Standards, W ashington, D .C .,M arch 1974.
[2] M .E . Senko, F ile Organization and M anagem ent Information S y stem s, Chapter 4,
Annual R eview o f Information S cien ce and T ech n ology, C. Cuadra, editor, V ol. 4,
E ncyclopaedia Britannica, C hicago, Illinois, 1969, pp. 111-143.
[3] F .W . L ancaster, O n-Line Information S ystem s, E ncyclopedia o f Library and Infor­
m ation S cien ce, V ol. 20, M arcel D ekker, N e w Y ork, 1977.
[4] F .W . L ancaster and E .G . F ayen , Information R etrieval O n-Line, M elville Publish­
ing C o ., L os A n geles, California, 1973.
[5] D . L efk ow itz, F ile Structures for On-Line S y stem s, Spartan B o o k s, R och elle Park,N e w Y ork, 1964.
[6] C. B ourne and B. A nderson, D IA L O G Lab W orkbook, 2nd Edition, L ock h eed In­
form ation S ystem s, Palo A lto , California, 1979.
[7] D IA L O G Information R etrieval Service, D atabase Catalog, L ockheed M issiles andSpace C o., In c., Palo A lto , California, M ay 1980.
[8] IBM W orld Trade Corporation, IBM System /370 (O S/V S), Storage and Information
R etrieval System /V ertical Storage (ST A IR S/V S) R eference Manual.
[9] Bibliographic Retrieval S erv ices, In c., BRS B ulletin, Schenectady, N e w York.
[10] N ational Library o f M edicine, On-Line S ervices R eference M anual, U .S . D epart­m ent o f H ealth, E ducation and W elfare, B eth esd a, Maryland, January 1980.
[11] N ational Library o f M edicine, M E D L A R S, T he Com puterized Literature Retrieval
Services o f the N ational Library o f M edicine, D epartm ent o f H ealth, E ducation andW elfare, Publication N IH 79-1286, January 1979. 'SYSTEMS BASED ON INVERTED FILES

49[12] D .B . McCarn, M E D L IN E : A n Introduction to On-Line Searching, Journal o f theA m erican S ociety for Inform ation S cien ce, V o l. 31, N o . 3, M ay 1980, pp. 181-192.
[13] System D evelopm en t C orporation, Highlights and Hints: ORBIT, System D ev elo p ­m ent Corporation Search, Santa M onica, California.
[14] System D evelopm ent C orporation, Search Service N e w s, N ew sletter o f the System
D evelopm ent Corporation Search Service, Santa M onica, California.
[15] J. R othm an, The T im es Inform ation Bank on C am pus, ED U C O M B ulletin, V ol. 8,
N o . 3, Fall 1973, pp. 1 4 -1 9 .
[16] The Information Bank, Thesaurus: A Guide for Searching the Inform ation Bankand for Organizing, Cataloging, Indexing, and Searching C ollections o f Information
and Current E ven ts, Parsippany, N e w Jersey, 1977.
[17] J. R othm an, T he N e w Y ork T im es Information B ank, The N e w Y ork T im es, N e w
Y ork, 1969.
[18] M ead D ata Central, L E X IS Quick R eference, N e w Y ork, 1976.

BIBLIOGRAPHIC REMARKS

Readers interested in learning more about the use of inverted files in various
areas of application may want to consult the following additional references:
G. W iederhold, D atabase D esig n , Chapter 3, B asic F ile System Organization, M cGrawH ill B ook C om pany, N e w Y ork, 1977.
C. M eadow , A pplied D ata M anagem ent, Chapter 3, D ata Storage, and Chapter 7, File
M aintenance, John W iley and S on s, In c., N e w Y ork, 1976.

For an elementary discussion of data structures see:
G .G . D odd, E lem ents o f D ata M anagem ent S y stem s, Computing Surveys, V o l. 1, N o . 2,
June 1969, pp. 117-133.

The following items relate inverted file systems specifically to information stor­
age and retrieval:
A .E . W essel, Computer A ided Information R etrieval, Chapter 9, C om puter Softwareand Som e Hardware C onsiderations, M elville Publishing C om pany, L o s A ngeles,
California, 1975.
C.J. van R ijsbergen, Inform ation R etrieval, 2nd E dition, Chapter 4, F ile Structures, Butterw orths, L ondon, England, 1979.

The operation of information retrieval systems using inverted files is describedin the following texts:
F.W . L ancaster and E .G . F ayen , Information R etrieval O n-Line, M elville Publishing
C om pany, L os A n geles, California, 1973.
F .W . L ancaster, Information Retrieval System s: C haracteristics, Testing and E valua­tion, 2nd E dition, Chapter 2, T he M atching S ubsystem ; Chapter 3, T he A pplicationo f C om puters to Inform ation R etrieval-O ff-Line B atch Processing S ystem s; Chap­
ter 4, On-Line Inform ation R etrieval, John W iley and S o n s, In c., N e w Y ork, 1979.

50

CHAPTER 2

The reader should be careful to distinguish books dealing with file structuresfrom texts covering principally data structures. There is some confusion in ter­minology between data and file structures and between lists, indexes, and files.
In information retrieval, the term data structure normally refers to abstract
constructs used to represent the entities and concepts under consideration—for example, documents, terms, and sentences. File structure, on the other
hand, refers to the organization of the document files and of the auxiliary files
used to access the main document files.

EXERCISES
2-1

C onsider the follow ing inverted index
T ER M A
TERM BTERM C

2-2
2-3

2-4

1,4,5,6,8
2 ,3 ,4 ,6 ,7 ,9 ,1 0
3 ,5 ,7 ,9Identify the docum ent num bers associated with each o f the follow ing retrieval
statem ents
a TERM A
AND
TERM Bb TERM A
OR
TERM Cc T ER M A
OR(TERM B A N D TER M C)
d TERM CNOTTERM AU sin g the inverted file structure from E xercise 2-1 describe a procedure w hich will
identify the docum ents in w hich TERM A is im m ediately follow ed b y TERM B.
If TERM A is assigned a w eight o f 2 by a particular user, and TERM S B and C are
assigned w eights o f 4 and 3 resp ectively, w hich docum ents will be retrieved byeach o f the follow ing statem ents, assum ing a retrieval threshold o f 6:a
TERM AORTERM Bb
TER M AORTERM BORTERM CcTERM BANDTERM CU sin g any programming language and an arbitrary tex t string consisting o f morethan one sentence d evelop a routine w hich creates an inverted index for the words
from the text and the associated sentence num bers. For exam ple, given the text:“ T he objects are p ro cessed serially. The first o f the objects b ecom es the represen­ta tiv e ,” the appropriate inverted index w ill be
TH E
OBJECTSARE
PR O C E SSE D
SE R IA L L Y
FIR STORBEC O M E S
R E P R E SE N T A T IV E

1
1
1
1
1
2
2
2
2

2
2

SYSTEMS BASED ON INVERTED FILES

2-5

2-6

51

Use the program created for Exercise 1-2 to isolate the individual words in the text
string.
Under what circumstances would it be reasonable to keep term location informa­tion in an inverted index? Given the example in Exercise 2-4, develop a routine tocreate an inverted index that includes term location information.
Create a routine which transforms the inverted index of Exercise 2-4 into alphabeti­
cal order.