X-l

ISR-7
June 1964
X.

PROCEDURES FOR STATISTICAL PROCESSING
AND REQUEST ALTERATION
Michael Lesk

1. Introduction
In order to find answers to requests, and to detect relationships
between concepts, it is necessary to evaluate the similarity between membersof a set of vectors*

These vectors may represent requests in a space ofconcepts; concepts specified by their occurrences in sentences; or documents. The SMART system contains programs for the evaluation ofrelationships between such vectors. These programs operate on rows of amatrix (each row representing one vector).

The values of the matrix elements

are the frequencies of occurrence of the row-column pair. That is, in the
document-concept matrix, the matrix elements represent the occurrences ofconcepts in documents; in the concept-sentence matrix, the elements represent the occurrences of concepts in sentences.
The programs to be described can produce a numerical measure of thesimilarity of two rows (their correlation), or a list of the rows
"significantly11 related to a selected row, or groupings of rows significantly
related to each other. Request answering is then performed by asking the
program to produce a list of the documents related to the request documents,using the correlations of the document-concept matrix. ' The matrices are
stored as chained arrays, and may thus be altered easily.

Alteration ofrequest vectors, for example, is readily performed by one of two possible

X-2
methods. One may use for this purpose preset relationships between
concepts, in the form of a hierarchy; or one may use statistical methods
to detect concept relationships. Vectors of requests may be either
expanded or contracted.
Since most of the internal data accumulated for each document
appear in the form of such vectors, the programs that process them are ofgreat importance. The present description is divided into two groups:
programs applying statistical procedures to obtain term and document
correlations, and programs handling the request processing.

2.

Statistical Programs
Statistical processing is done in SMART at three different times.

These are: term-term processing within a single document, document-document
processing when all documents have been read in, and concept-concept
processing using the distribution of concepts over the document collection.
The same basic programs are used in each case. The programs use aset of chained lists, one for each "row'1 in the matrix being correlated.
Two arrays are used. The first is a pointer array which includes one word
for each row, a FORTRAN integer giving the subscript in the second array of
the first matrix element of that row. Within the second array, called thedata array, each word contains three pieces of information:

the first nine

bits contain the numeric size of the element, the next twelve bits thecolumn number, and the last fifteen bits the subscript in this list of theX-3
next nonzero element in the same row ysee

Fig. 1 ) . These two arrays are

IfiOWST and FEEQ in the term-term correlation, MSTART and D0C1RD in the
document-document correlation, and IROWST and IWDLST in the concept-concept
correlation.
IRGWST-FREQ is set up by subroutine MATRIX from IWDLST, the input
text (see Flowchart 3) . The rows are concept numbers and the columns

12 3 4.567

matrix1
2
3

U

3 0 0 2 0 61
0 0 13 0 0 2
0 2 0 0 4 0 0| 1 0 1 0 0 1 0J

pointer array

1
2
3
4

1|

5;
:

3.
2 ',

-> 1
2
3
5
6
7
8
9
10
11
12

NOTE:

data a r r a y
3I l l 6
1 ! 4
11
21
2
8
1!
3
10
11
3 |
7
2<
4 | 9
3
4
| 12
!
5 | 0
4
6 | 11
6
6
|
0
1
7
1
0
i!
2)
7 1 0

1

This is only one of many acceptable representations of this matrix.

Encoding of an Occurrence Matrix
Figure 1/'The flowcharts appear in the Appendix to this section,

X-4
sentence numbers. MSTART-DGCWRD is accumulated as the documents are readin.

The row identifiers represent document numbers and the column markers

identify concept numbers* Transposing this, using subroutine TRANS yields
the IROWST-IWDLST concept-concept matrix.
Three methods are available for correlating these matrices, referred
to as cosine, matching or overlap, and asymmetric. When used to specify
the logical options, these are punched as COS, OVLAP, or ASYM, respectively.
Given two vectors x. and y., the coefficients used are:
1

COS
xy

J

r

E

x.y.

\Z4 S
Y

min(xi,yi;

OVLAP

xy

mm

(

H"i- H v) min(x i ,y i ;ASYM =xyy-r

i- ASIM ,yx>

as shown in Fig. 2. To perform these correlations, subroutine ROWSUM is used
to form the sums needed for the denominators (Flowchart U) • The correlation
mode is transmitted through location PARAM1, and the matrix locations function
as arguments for ROWSUM. ROWSUM leaves the sum of the elements (or theirsquares, as the case may be) of each row in array SUMSQ. ROCOR, shown in^ = 3 00 20

61~£ = 0 0 1 3 0 0 2

I>

Cos
r

ab

IS7

2 - 3 + 1-2

a2 Yb2I (9+4+36+1)( 1+9M)

CBin(al'bi — - 2 + 1

Ovlap
r

ab "

r-7

,—,

12

"

0,
""

mini

^min(a.,b.)Asymrab = —

^

^
= ^ =

-25

a.

i

2jnin(a.,b.)
r

ba =

^ ^
=

T ^

" 6 = *5b.
i

C o r r e l a t i o n Methods
Figure 2

Jvoo"

X-6
Flowchart 5, now performs the actual correlations using the same parameters
to determine the correlation mode. Each correlation is generated individually and sent to subroutines MCORR (if sense light 2 is on) and WGORR(if sense light 1 is on) . MCQRR stacks the correlations in a vector called
IVCORR for further processing; WCORR stacks them in an array called PAGE for
printing.
After each row is correlated, and its vector is stretched out in
IVCORR, subroutine FRIEND is called to decide which of the correlating rows
are to be considered "related11 to the given row. Currently, FRIEND merelycompares the correlations with a cutoff in KTEST; more sophisticated subroutines could, however, be substituted easily (see Flowchart 6 ) .

FRIEND

copies the list of related rows into consecutive words of IGROUP, packing
three 12-bit row numbers into one word.

It also puts a pointer in the

ISTART entry for that row, indicating the first word in IGROUP for thisrow (see Fig. 3) •This procedure continues until the rows related to every

row in the matrix are listed in IGROUP (the whole correlation matrix being
too large to store in memory).
For many purposes, the statistical processing is now terminated.
To obtain request answers, for example, the program can now produce thelist of related documents for each request from the IGROUP matrix.
Similarly, in concept-concept expansion, the program looks up the concepts
related to each concept in the request vector and adds them to that vector.
It is possible, however, to go one step further and try an elementaryclustering procedure. The list of "relations" may be considered as a kind

X-7^"""""•-^-^row
row 1

J

1

2

3

4

5

6

7

8

1

-

.5

.0

•9

.7

.1

.4

.3

2

.5

-

.9

.0

.8

.0

.8

•/

3
•
•
•

.0

.9

-

.0

.8

.0

.4

.3

(a) Correlation vectors r.
ij

apply cutoffrow

related to

1

U 5

2

3

3

2 5

(b)

5 7 8

L i s t of row r e l a t i o n s

ISTART
001
002
003

2 i
I

: i
• i

(c)

.6

IGR0UP
1
2
3
A
5

4-1
3
8

!

2!
1

ISTART - IGROUP
Formation of IGROUP
Figure 3

5

!
5
0|
51
1
1

"0
7
0
0

•• •

row
1
2

related to

3
U
5
6

u

5 7

6

9

1
1
3
1
1

7

8

9
4 8
U 7
3 6
7 8

7
8

9
10
11
12

8

10
10

12

7
(a) Relation list

2

11

•

•

10

(b)

Relation graph(c)

Final c l u s t e r s
(a)
(b)
(c)

3-6-9
1-4-7-8-10
leftover single

Formation of Clusters
Figure 1+

X-9
of graph, with lines connecting all related points. Subroutine CLUMP
accumulates maximal connected subgraphs from the connection data. Anotherprogram, CDENSE, reduces the size of each cluster by throwing out the ,fendsHof all branches (i.e., those points with only one connection to anothermember of the subgraph (see Fig. -4)). WCLUST will now print out thecluster; alternatively, CLSMAP converts term clusters into a form'usable forfurther processing.
In the concept-concept and document-document correlations, no use
is currently made of the clusters except to print them.

In the term-termcorrelation, however, the clusters can be used as phrases, and occurrencesof these clusters may be counted as pseudo-concepts. This is done by setting
up an array GLNUMS which indicates, for each term, the clusters to which it
belongs. The text in ITODLST is scanned, and for each sentence the sum of
the occurrences of members of each cluster is compiled in LITOCC. The entryof each cluster in LITOCC is now divided by the cluster size to determine
the number of cluster occurrences, which are accumulated for the document
in KLSGCC. This operation is performed by KCOUNT. Meanwhile, MAPKLS stillretains the information necessary to interpret the cluster counts^ i.e.,
the list of concept numbers in each cluster. This system may not be of muchuse when short documents are used, since all intradocument statisticaltechniques may then be of questionable applicability.

X-10
3. Request Processing
The SMART system, after processing all documents presented on the
input tape, proceeds with an interdocument operation specified by the
programmer. The major operation consists in the answering of requests andin the performance of the various request alterations.
The basic data useful for request answering is accumulated during
Phase II, the document absorption stage* During this stage the program
compiles the document-concept matrix, DOCWRD, which includes the conceptvector representation for all documents. This matrix is used together with
an auxiliary array called MSTARToMSTART contains one word per document;

this word is a FORTRAN integer giving the subscript I of the first element
in DOCWRD associated with the given document. Reference to DOCWRD(l)provides the first element of the document-concept vector, consisting of
one machine word divided into three fields. The first field gives theweight of this vector element, the second field stores the concept numberof this term (the column identifier of the element). The weight is generally
equal to the frequency of occurrence of that concept number in the text.
Concepts which do not occur in a given text are omitted from the vector, sothat no zero weights are included. The LOGICAL VECTORS (LV) option forces
all weights to become equal to 1 as the matrix is formed, thus suppressing
the frequency counting and correlating options• The final, third field of
the DOCWRD item gives the subscript of the next word in DOCWRD associatedwith this concept vector. By following the pointers In the third field, theentire vector may be readily obtained. A zero pointer indicates the end of
the vector.

X-ll
Other arrays used in processing requests include NAME1 and NAME2,
which provide the 12 BCD characters used to identify documents externally.
Internally, the program uses consecutive numbers assigned to the documents
as they are read in*

These numbers are replaced on printouts by the corre-

sponding 6-character words from NAME1 and NAME2. The identifiers stored
in these vectors are supplied with the document at readin time. Anotherimportant array is DFLAG, which contains one word for each document. This
word stores a nonzero address for each request document, a zero address for
nonrequests.
The first step in request processing is a straightforward correlation, using the same programs that serve for the term-sentence correlation.
Since the DOCWRD-MSTART combination uses the same format as the FREQ-IROWST
matrices, the identical programs suffice for both correlations; it is thennecessary only to change the addresses of the arrays to permit all internal
operations to be carried out correctly. For printout purposes, sense light
4 is turned on; this informs the program that Phas'e III is being executedand that row identifiers now represent documents and column identifiers
concepts. MAX, the parameter indicating the largest row identifier, is also
altered to represent the highest document number instead of the largest
concept number.
Correlation is under the control of subroutine DCORR, which calls
ROWSUM and ROCOR to perform the actual correlations. Three modes are again
available, specified by the logical parameter C0RMD3 and using the numericalcutoff CUT0F3. Correlations are printed by subroutines WCORR and WDCRND;

X-12
document-document relations are printed by WGROUP. To save time incorrelating, ROCOR correlates only those documents that have been marked
as requests if sense light 3 is on. Sense light 3 is set automaticallyunless the programmer specifies an option such as DOCUMENT CORRELATIONS(DC), DOCUMENT RELATIONS (DR), or CLUSTER DOCUMENTS (KD) . If only request
correlations are wanted REQUEST CORRELATIONS (RC) prints them. Request
relations - listing those documents considered "related" to a given
request - produces request "answers"; these "answers" are printed by
ANSWER REQUESTS (AR), probably the most common specification in the entire
system.
Since the initial answers are frequently unusable for one reason
or another, provision is made for altering requests and recomputing thecorrelations in the hope of altering the list of answers. Two basic
schemes are provided far the request alteration:

concept-concept correlationand hierarchical expansion, AS currently programmed, these options modify
only the request vectors; this is, however, a logical decision and theprogramming changes required to operate on all documents are slight.
Concept-concept expansion is a statistical technique. The system
attempts to add to a given request those concepts which, although originallyomitted, normally co-occur in the document concept vectors with the concepts
actually present in the request. The statistical processing is handled by
the same subroutine package that is used in the two other correlation
systems. The input matrix is the transpose of the document-concept matrix,
and gives for each document the occurrence,-frequencies of each concept.

X-13
Concepts are represented by the row identifiers, and documents by column
markers. The matrix is obtained by transposition of DOCWRD. Subroutine
TRANS performs the transposition; it uses the areas IWDLST, IROWST, andFREQ as storage space and generates an IWLST-IROWST pair of arrays identicalin format to FREQ-IROWST or DCCWRD-MSTART. Subroutine CQNCOR directs thecorrelation of this matrix by ROCOR and RCWSUM. Modes and cutoffs arecontrolled by parameters CQRMD2 and CUTQF2. The programmer can obtain, asintermediate output, the total number of occurrences of each concept byusing the CONCEPT FREQUENCIES (OF) option; similarly, the correlations canby obtained by specifying CONCEPT CORRELATIONS (CC), or the concept-concept
relations by a CONCEPT RELATIONS (CR) specification.
The actual expansion is performed by the use of the table of conceptconcept relations.(see Flowchart 8).

Subroutine SMEAR, using DFLAG, selects

all request vectors and calls subroutine LINEUP to extract them from thechained structure and line them up in convenient format.

Core area IVCORR

is used for the concepts and MAINSZ for the associated weights. SMEAR thenruns down the list of concepts in each request. Every concept islooked up in the concept relations table (which is again kept in ISTARTIGROUP matrices, as are the term-term relations and the document-document
relations), and its related concepts are added to the request vectors. If
the related concepts are already in the vector, the respective weights are
incremented. Subroutine FILLIN is used to restore the vectors into thechained format of DOCWRD for recorrelation. This process is specified by
the SMEAR CONCEPTS (SC) options. The vectors are printed before and after
expansion if the SMEARED VECTORS (SV) option is given.

X-lliThe second expansion method uses the hierarchical system. Subroutine TREES plays the same role here as SMEAR does in the concept-concept
expansion. It first calls each request in turn; the hierarchical programs
are then called to perform the vector alterations; finally, the adjusted
vectors are returned into DOCWRD (using FILLIN).

The HIERARCHICAL VECTORS(HV) specification controls the printing of "before and after" vectors. The
expansion is called if the specification HIERARCHICAL EXPANSION (HE) is
given (see Flowchart 7 ) .
The actual expansion is performed by the programs described inSec. V of this report.

Subroutine FOREST is called first to read thehierarchy from the library tape. Then one of four entry points is called,depending on the setting of the logical parameter GOTREE.

The possible

values of GOTREE are ROOT, which causes expansion by parents (subroutine
CLIMB); BRANCH, indicating expansion to sons (subroutine CHILD); FILIAL,
denoting expansion by brothers (subroutine FILIAL); and REFER, producing
expansion by cross references (CROSS).

These subroutines are called foreach request. An additional option decides whether the new concepts
provided by the hierarchy will be added to the existing concepts, or will
replace them.

This specification is the REPLACE BY HIERARCHY (RH) option.

The decision as to which hierarchical option is to be called is actually
made in CHIEF. TREES calls a general entry point named GEORGE, located in
the main program, which is set to CLIMB, CHILD, CROSS, or FILIAL, asrequired (see Fig. 5 ) -Concept

1 2

3 4

5 6

Weights

0

2 0

1 0

0

(a) Original request
Relations of concepts (from IGROUP)
concept

related to

1
2

2
1

3
U

U
3

5
6
Resulting request

3

Concept

1 2

3 4

5 6

Weight

0

3

1 0

0

2

(b) Concept-concept expansion

Expand by parents; resulting request
Concept

1 2

3 4

5 6

Weight

3

6

1 0

0

2

(c) Hierarchical expansion
Request Alteration
Figure 5

X-16

After expanding all requests, DCORR is again called to recorrelate
the request documents. If a correlation printing option is given, therequest correlations are printed again. The subroutine REQUST is thencalled ,to print the new answers. These may now be compared with theprevious set, and the effectiveness of the expansion method may be studied.

X

APPENDIX

Generate encoded
occurrence matrix.
MATRIX; FILLIN; TRANS

Perform row correlations ROWSOM;
ROCOR

Print correlations if
desired. WCORR
Compare correlations
with cutoff. Form
IGROUP matrix. FRIEND

Cluster. CLUMP

Print portions of IGROUPWGROUP

Statistical Processing
Flowchart 1

Perform document-document
correlation. ROWSUM, ROCOR
Prepare list of documents related
to each request. FRIEND

iL
Print "answers."

REQUST

3L

NO

Was concept-concept expansion r e q u e s t e d ? / *YESTranspose document-concept matrix toform concept-document matrix. TRANS
Correlate, obtaining concept-concept
correlations and relations. ROWSUM, ROCOR
iL.

Add to each request concepts related toj
any concept in the request. SMEAR±-

Recorrelate requests vs. documents andprint new answers.

<

NO

T
\^ Was hierarchical processing requested?/*Add to each request concepts hierarchicallyrelated to concepts in the request. TREES
Recorrelate, print new answers.
(EXIT)

Request Processing
Flowchart 2

X-19

-*

Get looked-up t e x titem from ITOLSTExtract next concept
number found in lookupi

YES<ls it = 0?)NOYESk^'ls it±1000f>NO

J*L

Does IROWST contain an
entry for this concept?

YES

NO

y.._

Set IROWST pointer for thisconcept to the next empty
location in FREQiL
Set next location of FREQ toa data word indicating one
occurrence of this concept
in the current sentence.
</Are there more concepts for\\ t h i s w ord V/
YES,<^Are t h e r e more words i n text?~>

NO
ReturnMATRIX
Flowchart 3

Go to indicatedelement of FREQ.

±. to next, Get pointerNO / T r . ._element, if any. Is
this the last FREQ entry t^for this concept?
.YESy'Is the sentence
0 / number of thisentry = current\text sentence number?/Raise count of occurrencesof this concept in thissentence by one

Set current
row counter = 1

Is entry in pointer\array for this row = 0?/^NO
Extract successive data
items from data arrayfor this row,
accumulating eitheriidepending on PARAM1*ROWSUM
Flowchart 4

YES

X-21
Initialize IROW
counter_±

X* Is IROW pointer = 0?)NO
Initialize JROW
counter*-X Does JROW pointer = 0'>>NO<(~ Does" IROW = JROW? )s/

Get new data item for^flRQW. Contains: column
marker, weight.
J*L
Compare column markers
IROW, JROW data items
Column (IROW) <Column (JROW)YES

Any more
IROW data:noColumn (IROW) =Column (JROW)U

Column (IROW) >Column (JROW)

Combine weights,
accumulating
cross term(either w. * w.
or min(w.,w.)J
l' J

*
N
Kkny more JROTff data?yYESNO
Get next JROW data

{Any more JROWS?
YES
Go to next JROW |Compute correlation
using SWMSQ
P r i n t s sendt o FRIEND
ReturnNO

I ~~-{Any more JROW?)
Go t o next IROW

ROCOR
Flowchart 5

X-22

Receive correlation
vector from ROCOR

Jr
Compare correlations'against cutoff

Y
Prepare list of rows
related to this row
in matrixi
Find first free location in
IGROUP. Put pointer tothis location in ISTART's
entry for this row,,. ^ fCopy list of rows related
to this row into IGROUP
starting at first freelocation<(
Return to ROCORFRIEND
Flowchart 6

Begin scanning listof documents
->\

-¥NO

Is this documenta request?

YES±

Extract concept-vector
from DOCVffiD-V.

Print concept-vector |if sense light 1 on j

J
Gall hierarchical programs
to alter vector of request
Y
Print concept-vector
if sense light 1 on

*L
Copy concept-vector
back to DOCWRD±/ Is this the last
document?

NO
Continue scanninglist of documents

TREES
Flowchart 7

24>fScan l i s t of documents

NO

itIs this document arequest?

YES
Extract concept-vector.
Print if sense light 1 on |JL.
For each entry in concept-vector;
extract from IGROUP all concepts
related to it. Add theseconcepts to the vector.

Copy c o n c e p t - v e c t o r back t o
DOCYOID. P r i n t i f sense l i g h t
1 on

-M

m

Is this the last document?L>YES
ReturnSMEAR
Flowchart 8