ISR-9
August, 1965

XIVo

XIV-1

Concept-Concept and Document-Document Correlations
M* Cane and G« Shapiro

1oIntroduction
This section describes the algorithm employed to perform concept-concept and document-document correlations. The algorithm uses a tape containing a number of vectors and correlates each vector with all of theothers; all correlations exceeding a user specified cutoff value are written
outo

The user also specifies the correlation mode (either cosine or overlap)

to be employed in performing the correlations. The general method is tofirst fill a buffer with as many vectors as possible, correlating each ofthem with the others in the buffer*

After the buffer is filled^ the remain-ing vectors on the input tape are passed through and correlated with all thevectors already in the buffer. As the vectors are correlated they are
written out onto a new tape. After all vectors on the first tape have beenprocessed in this manner, the vector tape just created is used as the input
tape for the next correlation pass*

The vectors on this new tape are again

read into a buffer and correlated with each other. When the buffer isfilled,, the remaining vectors are again passed through core and written onto
a new tape,. This process continues until all vectors have been correlatedwith all others,,
Part 2 of this section describes the operation of this algorithm ingreater detail. Part 3> which follows, describes how the algorithm is used
for concept-concept correlations. The final part discusses its application

XIV-2to document-document correlations,
2.

Correlation Algorithm
The general outline of the correlation algorithm is shown within thedotted lines in Flowchart 1. Each call to SPASSI or CCPASS corresponds to acorrelation pass —i.e., the correlation of a single buffer load of vectors

with all the vectors that remain.
Subroutine GPASSI executes the first correlation pass.
arguments: NIT, NOUT, N2T, IDCCUT, IFIN, and ITERCT.

It uses six

NIT is the logicalnumber of the input tape; NOUT is the number of the tape which is to receive
the correlations which are written out; N2T is number of the taoe which receives the vectors that didn't fit into the buffer space; IFIN is set to nonzero by CPASSI only if all vectors have been correlated with all others.
IDCCUT and ITERCT control the format of the input tape for the concent-concept
correlations; these are explained in the next part.
Subroutine CPASSI is described in Flowchart 2. The operations ofCPASS 1 may be understood more easily if the subroutines called by this routine are examined first:(1) CFETCH and LFETCH. CFETCH is an initialization entry for
LFETCH.

It has five arguments—NIT, IWH, ICON, ITERCT andIDCCUT.

NIT, ITERCT and IDCCUT are identical with the argu-ments to CPASSI. LFETCH will return a code to IWH and an
identifier to the two word FORTRAN array ICON. When LFETCH
is called it returns the next vector entry to the accumulator.

(Each vector entry has a concept number in the decrement

SET INITIALVALUES OF
LINK PARAMETERS
ITERC

5CALCULATE NUMBER
OF FILES OF
DOCUMENT TAFETO BE SORTED

12CALL SPECTR TO
SORT THE TAPE INTO
CONCEPT ORDERNRT I S THE SORTEDTAPEAYESIS
EXPANSION^.ON REQUESTS
ONLY?.

NO

TAPE TO BE
SAVED-NTBS= BlTAPE TO BESAVED-NTBS= NRTCALL TCH003 TO
FIND TAPES FOR
SORT, OUTPUT,SWITCHING

SUPER9 - SUPERVISOR FOR LINK 9FLOWCHART 1r
CALL CPASS1 (NRT, NOUT,N2T, IDCCUT, IFIN, ITERCT)FOR FIRST CORRELATING PASS

21RESET TAPESSWITCH NITAND N2T

CALL CCPASS (NIT, NOUT, N2T, IFIN)FOR NEXT CORRELATIONPASS

30CALL CNDFIN
TO FINISH
OUT PUTTINGCORRELATIONSIFLOWCHART 1 (CONTINUED)XIV-5CALL SPECTR TOSORT OUTPUT INTO
CONCEPT-CONCEPTORDER

ITERCT - ITERCT + 135
SET CORRELATIONMORE AND CUTOFFFOR ITERATEDCASEYESREWIND TAPESCALL ENDENDTO TRANSFER TO
LINK 10FLOWCHART 1 (CONTINUED)XIV-6and a weight in the address.) LWH is set to 2 if the present
entry is the last entry of the vector, and to 3 if it is thelast entry on the tape. It is set to 1 otherwise. When IWHis 2, ICON will contain the identifier for the next vector.
(2) The other subroutines act on an array of five word items
called IDOCWD. The first two words of each item contain theidentifier for the vector. The decrement of the third word
is the index in the buffer IVEC of the first word of thevector; the address points to the word following the lastword of the vector. These items are put into the array by
the program that fills the IVEC buffer (CPASS1 in this case).
The fourth word of the item is the denominator for the vector.

It is entered in the Ith item of IDOCWD by calling

DENOM (I).

If IENOM is called with a negative argument, apartial denominator is formed since the vector given is notcomplete, so that a full denominator cannot as yet be calculated. The fifth word of each item is entered into thearray by subroutine CORREL. Calling CORREL (I) causes thecorrelation of vector I with vector J to be entered in thelast word of the Jth item of IDOCWD, for J £ NREQ. NREQ
identifies a location which is 99 words down from the top ofcommon. When CORREL is called with a negative argument apartial correlation is performed.
(3) CNOUT searches IDOCWD and writes out all correlations above
the cutoff value. Two arguments are used: The first is thelogical number of the output tape; the second is I, the index of the item in IDOCWD which is being correlated with theNREQ vectors.
The section of CPASS1 from box 10 of Flowchart 2 up to box hO fills abuffer named IVEC and correlates these vectors with each other. ThreeINITIALIZE CALL CFETCH

10PICK UP IDENTIFIER AND STORE IN IDOCWD

11MOVE NEXT ITEM TO IVEC BUFFER WITH LFETCH

JiL- 3- 1--H SET EOF
FLAG

152E3.

CALL DENOM TO CALCULATE
DENOMINATOR, CORREL TO
CORRELATE, CNOUT TO OUTPUT2k I
CALL MOVOUTTO HANDLE RECORD
LENGTH PIECES OF VECTORCALL DENOM L - 1 0NO.65IFIN - 6RETURN

YEStelMOVE REST
OF VECTCRTO IBUNBUFFERPICK UP IDENTIFIERAND STORE IN IDOCWDJtL
MOVE NEXT ITEMTO IBUN BUFFER WITH LFETCHid

CALL DENOM(-ID)
AND SETIBUN ( U 9 8 ) = 0i4_•1SET EOF
FLAG

LWH- 2_ki

CALL DENOM AND STOREANSWER IN IBUN (COUNT+l)
ICOUNT = ICOUNT • 1w

SUBROUTINE CPASS1FLOWCHART 2

END LAST OUTPUT TO N2T !
STORE IDENTIFIER INTOIBUN FROM IDOCWD
START NEW OUTPUT TO N2TCALL CORRELNOYES51
CALL CNOUTNOV 60,END OUTPUT'
TO N2T

IFIN - 0

IFIN - 6

RETURNFLOWCHART 2 (CONTINUED)XIV-9conditions cause control to be transferred out of this sections(1) The input tape is exhausted.

In this case all vectors

have been correlated so IFIN is set greater than zero,(2) The IDOCWD buffer is filled. Control then passes tobox UO.
(3) The IVEC buffer is filled. Control is eventually transferred to the section beginning at box UO, which creates
the vector tape for the next pass. First, however, it
may be necessary to start this tape by writing out initial
pieces of the vector that were put into IVEC. Subroutine
MOVOUT accomplishes this.
The section of code beginning at box I4O is essentially the same as thecode that preceded it, with the important difference that it also writes out
the vectors. Each vector is written out in records not larger than 500 words.
The first two words of each record contain the identifier for the vector; thethird word contains the denominator if this is the last record of the vector;
it is zero otherwise. The remaining words contain the vector entries.
Subroutine CCPASS has four arguments —NIT, NOUT, and IFIN, correspond-ing to the arguments of CPASS1. CCPASS is very similar to CPASS1 as can beseen from Flowchart 3; the difference is that CCPASS has to deal only withthe vectors in the form created by CPASS1. All entries are already set up,
the denominators are all calculated, and so on.
All 1-0 is double buffered, and it makes use of the INOT trap controlled input-output routine.

XIV-10INITIALIZE
START READ OF N2TIJ£_END ROAD
OF N2T

IFIN-6
RETURN

YES'START NEXT
READ OF N2T

YES

17SET IDENTIFIERS
IN IDOCWDNOWILLTHIS RECORDFIT IN THEJUFFER^

YESrNOMOVE IT
INTO BUFFERYESNOCALL MOVOUTTO WRITE LASTPIECE OF DOC.
ONTO N2T

21SET POINTERS
AND DENOMINATOR
IN IDOCWD

2$_CALL CORRBL TO CORRELATECNOUT TO OUTPUTNO

IS IDOCWD FILLED?

YES

J21.

SET FREE SPACE POINTER SONO MORE VECTORS WILL FITSUBROUTINE CCPASSFLOWCHART 3XIV-11iko_END OUTPUT
OF DOCUMENTVECTOR TO N2TU2END INPUT OF
DOCUMENT VECTORFROM N2T AND BEGIN
NEW INPUTIF EOF

J±6_START OUTPUT
OF VECTOR TO N2T

IFIN=0

IFIN-6RETURNSET UP JDENT.,
AND POINTERS
IN IDOCWB

YES-_klNO

CALL CORRELL(-IO)
FOR PARTIAL
CORRELATIONFLOWCHART 3 (CONTINUED)CALL CORREL ( 1 0 )FOR CORRELATIONAND CNOUT TO OUTPUT
IC0UNT=IC0UNT+1

XIV-12

3. Concept-Concept Correlation
The input to the concept-concept correlation link is a tape (Bl) filledwith two word items: the first word contains a concept number and a weight,
packed in decrement and address; the second word contains the document numberin the decrement. There document numbers are created by link 8. The tapealso contains entries for which the last bit of the address field of thisword is "on." In this case, the first word contains the actual BCD name ofthe document.
This tape is sorted into concept order:
The document-concept matrix that was on the tape is then effectively transposed into a concept-document matrix. For each concept number LFETCH will
return vector entries which contain the document number in the decrement andthe weight in the address. Then vectors are then vectors of documents allidentified by a given common concept. LFETCH ignores all items whose document numbers are less than IDCCUT. Since IDCCUT is set to the highest
numbered request; the effect is to ignore all occurrences in requests.
The output routine CNOUT sets up two word items. The first contains
the numbers of the two concepts whose correlated was higher than the cutoff
value; these are packed two to a word. The second word contains the correlation coefficient. CNOUT double-buffers its output, only outputting when abuffer has been filled. CNOFIN is a final entry which writes out all items
that are waiting in the buffer when correlations are completed.
After the concept-document tape has been completely correlated, theoutput tape is sorted into order according to the first word of each item

XIV-13(that is5 on the concept-concept word).
At this point it is possible to iterate the concept-concept correlations o The sorted output tape may be viewed as concept vectors over thespace of concepts. When CFETCH is called with ITERCT greater than one, itexpects the input tape to be a concept-concept tape. It takes the first halfword (the first concept number) as the vector identifier, and the second halfword as the decrement of the vector entry. Each entry is assigned a weightof 1 (in the address field); thus the concept-concept matrix becomes a binarymatrixo

The results of each correlation are iterated in this manner until

ITERCT equals CONCON, Control is then transferred to link 10.

U. Document-Document Correlation
The document-document correlation program attempts to find out whichdocuments in the input collection are closely related by correlating theirconcept vectors. In practice, either overlap or cosine correlations are permitted. The main use of the document-document correlation is to expand request answers by including along with each document in the answer all documents which correlated with it above some fixed cutoff.
The basic algorithm used for document-document correlation is thesame as that described in Part 3 of this section. The document-document
programs are simpler in certain respects, the basic simplification beingthat the document-vector tape, as produced by the lookup, is already insorted order so that no tape sort need be used initially„is made for iterating concept-concept correlations.

Also, no provision

XIV-lU

The document-document programs use the same routines CCPASS, CPASS1,and MOVOUT that are also used by the concept-concept programs. The programs
CFETCH, LFBTCH and CNOUT which they call must, however, be different sincethe formats involved are different.
The document-vector input tape contains 200 word records. Each word isof the form
CONNO.

WEIGHT|

where CON NO. is a concept number and WEIGHT a weight. The individual document vectors are sorted on the concept number. The last word of a document
vector is a word of zeroes, used as a flag. The last record of a document
may be short. Bach document is preceded by a 12-word record containing BCD
identification. The versions of LFETCH and CFETCH used by the documentdocument programs accept this new format but otherwise they act in the same
way as the versions earlier described. When a new document is started, LFETCH
returns the second and third words of the BCD identifier as identification tothe calling program.

These two words are later written out by CNOUT with thecorrelation.
The output tape for the document-document correlations is written inrecords containing 100 five-word items. Each item looks likewd2

35m iCorrel

DOCtNM 2

where correl is the two's complement of the correlation between documents

xiv-15

with identifiers DOCNML and DOCNM2. This output task is performed by a modified version of CNOUT. This program writes out only those items with a correlation above a user supplied cutoff*
After the correlation has been completed, the output tape is sorted
by SFBCTK into document order. The correlations are complemented so thatthe sort will order the documents correlating with a particular document indecreasing order of correlation. This sorted tape is then used to expand
the request-document correlation tape. This correlation tape has the same
five-word item format as that mentioned above. It is sorted into documentorder, a simple double-buffered merge is performed to combine it with the
document-document tape, and the output tape is then sorted back into request
orderoThe section ofFlowchart 1

enclosed in dotted lines represents thesupervisor program also for the document-document correlation. The merge
mentioned above is completely straightforward. All sorts are done using thetape sort SPECTRc