II-lII.

A Scatter Storage Scheme For
Dictionary Lookups
D. M. Murray1#

Introduction
A document retrieval system must have some means of recording the

subject matter of each document in its data base.

Some systems store theactual text words, while others store keywords or similar content indicators.
The SMART system [1J

uses concept numbers for this purpose, each number

indicating that a certain word appears in the document.

Two advantages areapparent.

First, a concept number can be held in a fixed sized storage

element.

This produces faster processing than if variable sized keywords

were used.

Second, the amount of storage required to hold a concept number

is less than that needed for most text words.

Hence, storage space is used

more efficiently.
SMART must be able to find the concept numbers for the words in any
document or query.

This is done by a dictionary lookup.

reasons why the lookup must be rapid.

There are two

For text lookups, a slow scheme Is

costly because of the large number of words to be processed.

For handlinguser queries in an on-line system, a slow lookup adds to the user response
time.
Storage space is also an important consideration.

Even for moderate

sized subject areas the dictionary can become quite large — too large forcomputer main memory, or so large that the operation of the rest of theretrieval system is penalized.

In most cases a certain amount of corestorage is allotted to the dictionary, and the lookup scheme must do theII-2

best possible job within this allotment.

This usually means keeping theoverhead for the scheme as low as possible so that a large portion of theallotted core is available to hold dictionary words.

The rest of the dic-tionary is placed in auxiliary storage and parts of it are brought in as
needed.

Obviously the number of accesses to auxiliary storage must be

minimized.
This paper represents a study of scatter storage schemes for application to dictionary lookup.
servative with storage.
schemes in general.

These methods appear to be fast and yet con-

The next two sections describe scatter storage

The fourth section presents the results of various

experiments with hash coding algorithms.

The fifth section discusses thedesign and use of a practical lookup scheme.

The final sections deal withextensions and conclusions.

2.

Basic Scatter Storage
A)

MethodA basic scatter storage scheme consists of a transformation algorithm
and a table.

The table serves as the dictionary and is constructed as follows.

Given a natural language word, the algorithm operates on its bit pattern toproduce an address, and the concept number for the word is placed in the tableslot indicated by this address.
be placed in the dictionary.

This process is repeated for every word to

The generated addresses are called hash addresses;

and the table, a hash table.
There are many possible algorithms for producing hash addresses. [2,3,4]Some of the most common are:1)choosing bits from the square of the integer represented by

II-3

the input word;2)

cutting the bit pattern into pieces and adding thesepieces;3)

dividing the integer represented by the input word by thelength of the hash table and using the remainder.

BX

Collisions

The ideal situation would arise if every word placed in the dictionary
had a unique hash address.

However, as soon as a few slots in the hashtable have been filled, the possibility of a collision arises — two or more
words producing the same hash address.

To differentiate among collided

entries, the characters of the dictionary words must be stored along with
their concept numbers.

Then during lookup, the input word can be comparedwith the character string to verify that the correct table entry has been
located.
The problem of where to store the collided items has several methodsof solution. [3]The linear scan method places a collided item in thefirst free table slot after the slot indicated by the hash address.

The

scan is circular over the end of the table.

The random probe method uses

a crude algorithm to generate random offsets

R(i)

where

H

is the length of the hash table.

slot

A+R(l) mod H

slot is found.

is examined.

in the interval[1,H]

If the colliding address is

A ,The process is repeated until an empty

Both of these methods work best when the hash table islightly loaded, that is when the ratio between the number of words enteredand the number of table slots is small.

In such cases the expected lengthof scan or average number of random probes is small.
Chaining methods provide a satisfactory method of resolving collisions regardless of the load on the hash table.

However, they require aII-4

second storage table — a bump table — for holding the collided items.

When acollision occurs, both entries are linked together by a pointer and placedin the bump table.

A pointer to this collision chain in placed in the hashtable along with an identifying flag.

Further colliding items are simply

added to the end of the collision chain.

C\

Table Layout and Search. Procedure

In the virtual scatter storage system described later, the hash table
has a high load factor.

Hence the chained method (or rather a variation ofit) is used to resolve collisions.

Further discussion involves only scatterstorage systems using collision chains.

With this restriction, then, ascatter storage system consists of a hash table, a bump table, and the associated algorithm for producing hash addresses.

A dictionary entry consistsof a concept number and the character string for the word it represents.
These entries are placed in the hash-bump table as described above.

Conse-

quently there are three types of slots in the hash table — slots that are
empty, slots holding a single dictionary entry, and slots containing apointer to a collision chain held in the bump table.

A typical table layout

is shown below.

Hash Table
empty slot

Concept + Char.

Pointersingle dictionary entry>

Entry 1

Collision Chain

Entry 2
•

>

II-5

One of the advantages of scatter storage systems is that the searchstrategy is the same as the strategy for constructing the hash-bump tables.
Given a word, its hash address is computed and the tables searched to findthe proper slot.
slot.

During construction, dictionary information is placed in the

The basic search procedure is illustrated by the flow diagram in

Fig. 1,

The construction procedure is similar.

D\

Theoretical Expectations

An ideal transformation algorithm produces a unique hash address foreach dictionary word and thereby eliminates collisions.

From a practicalpoint of view, the best algorithms are those which spread their addresses
uniformly over the table space.

Producing a hash address is simply theprocess of generating a uniform random number from a given character string.
If the addresses are truly random, a probability model may be used to predict various facts about the storage system.
Suppose a hash table hasHentered in the hash-bump tables.

Lettable slots withi = 0,1,...Nientries forthe expected number of empty slots,
entries, andE ,E ,...,E N

numbers of colliding items.

H.

slots and thatE

N

words are to be

be the expected number of hash.

In other words

H

isis the expected number of single

are the expected number of slots with various
Even though the it€ims are physically locatedin the bump table, they may be considered to "belong" to the same slot in
the hash table.
It is expected that:NCD

E = I Ei=0N

C2> N =; I i E.
1=0

*•

II-6

Input theText Wordx

ComputeHash Address-Empty -"Pointer"

Dictionary

±

>

JSl£

Get Next
Bump Table
Entry

No

Yes

±

Yes
T>

ReturnConcept
NumberFlow Diagram for the Lookup Procedure in
Basic Scatter Storage Systems

Fig. 1-^

Word NeverEntered in
Dictionary

II-7

Now letll if exactly i items occur in the jslot=\
0 if exactly i items do not occur in the j

X

slot

for j = 1 5 2,• . . , H

Then

H. = E L{X.. + X.n + . . . + X.uj}
I
xl
x2
iE

= I E {X 11]

j=lAssume that any chosen table slot is independent of the others sothat the probability of getting any single item in the slot is
the probability of getting exactlyi^ \-\im u-ir
Then

1/H . Thenitems in that slot is1

E { x . . } = 1- P. + 0 ( 1 - P . )
l]

i

i

P.

Substituting into the aboveO)

H. = H-P.
I

I

1 for i=0,1^fl^rM)"
For the cases of interestHandtion can be used in equation C3):
P. = e- N / H
1CN/H)1
7-i

N

""

H
,

are large, and the Poisson approxima-

II-B

The ratio

N/H

designated by(5)

is the load factor mentioned previously.
a

It is usually

so that

H. = H e" aa1

i = 0,1, . . . , N

In a form more convenient for hand computation

H

= e

o

H. = H. ,-%Ii-l I

i = 1,2, . . . , K

Equation C5) is sufficient to describe the state of the scatter storage
system after the entry ofN

items.

Most of the statistics of interest

can be preducted using this expression; a few of them are listed in Table 1.
The time required for a single lookup using a hash scheme depends on
the number of probes into the table space, that is, how many slots must be
examined.

Suppose the word is actually found.

only one probe is required.

If it is a single entry,

If the word is located in a collision chain, thenumber of probes is one (for the hash table) plus one additional probe foreach element of the collision chain that must be examined.
word is not in the dictionary.

Suppose that the

If its hash address corresponds to an empty

table slot, again only one probe is needed.

However, if the address points

to a collision chain, the number is one plus the length of the chain.
For words found in the dictionary the average number of probes per
lookup is:(8)

P = 1 + jjj- {(0)H„+ Cl+2)H2 + tl+2+3)H3 + . . ,i= 1 + I &*
IJ
L
1=2

j=l

+ Clt2+.„tNlH N i

II-9

MeasureLoad factor

Formulaa = N/E

Number of empty table slots
Number of single entries
Number of collision chains oflength i

H x = N e" ai' H. = H e" a -_2-T^.• - 9 0
X -^ , 0 , , . . ,N

X

N
E = y

Expected sums

.L
1=0

E.
X

N

N = y iH.
1=0

Fraction of hash table empty

F =k
0

E

= e-a
0

ae

Fraction of table filled withsingle entries

F

Fraction of hash table slots
with i entries

F. = rr H. = e
JL
a. xl = E Hl =

-a

-a

a

i=2,3,. ..,N-TT

N

1 - .IL F.x

Expected sums

1 =0

N

a = yL.
x=o

Number of collisions

i F.

x

Nc = H 2 + H 3 +... + H N

= H. - H0

Number of entries in the bumptable

B = N - H

Total table slots required

S = M t B

Average lookup time Cprobes)

P = 2 + « - e-a

E = number of hash table slots
N = number of words to be entered

Expected Storage and Search Properties for
Basic Scatter Storage Schemes
Table 1- H.
1

11-10

1

H n

H

+£ I

- iCi+DH
N i. = 2n Tfl-

1

i+2i

I t i

1

X

N

I

iCi + DFi=2NI(i+l)F. .

A £_2

N

1 +

N

a

lj2 -

1 ) F

+

[ = 2 F i-l

i-l 2

N+l

1+

N+l

Ci 1)F i + 7

2L2 " -

L2Fi^

1 + - a + Cl-F )2 + —- a - e

3.

Cprobes)

Virtual Scatter Storage
A)

MethodFrom Table 1, the expected number of collisions isN= H - H
c

o

- tL
1

= HCl - e

For a fixed

N

-— e

)

, this number decreases asHincreases.

At the same tine

the number of empty hash table slotsHo= H e"N/H

increases asHincreases.

Bothof these results are expected — as the11-11hash addresses are spread over a larger and larger table space (H slots),
the number of collisions should decrease and the number of empties increase
for a fixed number of entries (N).
A virtual scatter storage scheme tries to balance these opposing
strains by combining hash coding with a sparse storage technique. Largeor virtual hash addresses are used to obtain the collision properties associated with a very large hash table, and the storage technique is used toachieve the storage and search properties of a reasonably sized hash table.
If the virtual hash address is taken large enoughthe expected number ofcollisions can be reduced to essentially zero. With no expected collisions,
it is possible to dispense with verifying that a query word and the dictionary word are the same.

It is enoughto check that they produce thesame virtual address. Hence, the character strings need not be stored in
the hash-bump tables at all.
To implement the virtual scheme a large hash address is computed,
say in the range [0,V], and is split into a major and minor part. The
major portion is used just as before — as an index on a hash table of size
H.

Instead of storing the character string in the hash or bump table, theminor portion is substituted.

With this difference, the virtual scheme

works just as the basic scheme.

The lookup procedure is identical, but

the minor portions are used for comparison rather than character strings.
All the results of the previous section apply as storage and timing estimates.
The advantage of virtual scatter storage systems is economy ofstorage space.

The size of the minor portion is much smaller than the sizeof the character string it replaces.

It is true, that the virtual scheme

11-12

assigns the same concept number to two different words if they have the same
virtual address. This need not be disastrous for document retrieval applications.

PresumablyVis chosen large enough to keep the number of colli-

sions small. On the one hand, errors could be neglected because of their
low probability of occurrance and their small effect on the total performanceof the retrieval system.

On the other hand, it is always possible to resolve

detected collisions even in a virtual scheme. Collisions may be detectedduring dictionary construction or updating, and the characters for the colliding words appended to the bump table. The hash or bump table entry must
contain a pointer to these characters along with an identifying flag. Collisions occurring during actual lookups cannot be detected.
B) Collision Problem
In order to use a virtual hash- scheme, the virtual table must belarge enough to reduce to expected number of collisions to an acceptablelevel.

From a practical point of view, a collision may be considered to

involve only 2 words, rather than 3, M-, or more.

It Is assumed that theprobability of these other types of collisions is negligible*

Let

V be

the size of the virtual hash table. Then the expected number of collisions
is simplyNc = H2
2
-V-

where

e

a = — . In this casemately 1.,

V>>N

so thata

is small ande

is approxi-

11-132(9) N= V 5Lc2
N2
2V

Suppose, for example, the dictionary has

13
N = 2
words.

If the1)fsize of the virtual hash table is chosen to be

V = 2, then the expected

number of collisions isc(213)2
2C226X

1
2

Suppose further that this table size is adopted for the dictionary, and thatthe hash code algorithm produces 3 collisions.

The question arises whether

the algorithm is a good one — whether it produces uniform random addresses.
The answer is found by extending the previous probability model.
Consider a virtual scatter storage scheme in which the virtual tablesize isV , andN

items are to be entered into the hash-bump tables.

Again assume that collisions involve only two items.

LetP(i) = Prob {i collisions}= Prob {i table slots have 2 items and N-2i slots
have 1 item}

The number of ways of choosing theipairs of colliding words Cin anordered way) is:fN[N-21 . . .

N-2i+2|2 1 01-211!

There arei! ways of ordering these pairs and11-14v:(v)„'N-i. =' CV-N+i}!

ways of placing the pairs in the hash table, so that(10) P C i )% i . , (N-2i)l2-ij <-« " ' •-^rfori=a,l,...,L|j

In a form for hand computation,en)PCO) = a - i-x a - fi . . . a - ^~iPCX) = P C I - i )2iCv-N+iy

for

x =

1

»2."-»LyJ

These results are exact, but the following approximations can be used withaccuracy

N-llog PCO) = I

log Cl -

^

N-l

si
2V
Let

3

N
= — •

Terms l i n e a r in. •N may be n e g l e c t e d in equation (11) g i v i n g

PCO) = e~ 6PCi) = I PCi-l>
This i s a l s o a Pois-son d i s t r i b u t i o n :C12)PCi) = e-® Ca.:^r

i=0,l,2,...,L|j11-15This equation gives the approximate probability ofvirtual scatter storage scheme.

icollisions for a

It may be used to form a confidence

interval around the expected number of collisions
For the previous example in which

V = 2

N

= 6.

, N = 2 ' ^ N~y5

the following table of values can be made:

i

PU>

£PCU

0

.607

.607

1

.303

.910

2

.076

.986

3

.012

.998

The probability is .986 that the number of collisions is less than or equal
to 2.

Since the algorithm gave 3 collisions, it appears to be a poor one.

The results for the collision properties are summarized in Table 2.

4.

Experiments with Algorithms for Generating Hash Addresses
Any scatter storage scheme depends on a good algorithm for producing

hash addresses. This especially is true for virtual schemes in which collisions are to be eliminated.

In these experiments three basic algorithms

are evaluated for use in virtual schemes.

The words in two dictionaries —the ADI Wordform and CRAN 1400 Wordform — are used.

The hash-bump tables

are filled using these words and the resulting collision and storage statistics compared with the expected values.
A) Dictionaries
The ADI Wordform contains 7822 words pertaining to the field of docu-

11-16

MeasureFormulaB-N2

Collision factor

6

Expected number of collisions
Probability ofi collisions

Probability that the numberof collisions C lies
in [a,b]

1

' IT

N = 6
c

PCi) = e~e |ibProb = I P(i)i=aV

virtual hash table sizeNnumber of words to be entered

Expected Collision Properties for
Virtual Scatter Storage Systems

Table 2i=0

* !

11-1/

mentation.

It contains 206 common words (previously judged) averaging 3.93

characters.

The remaining 7616 noncommon words average 8.00 characters.

In all there are 61,712 characters.
The CRAN 1400 Wordform contains 8926 words dealing with aeronautics.
The common word list consists of that of the ADI, plus four additional entries.
The 8716 noncommon words average 8.40 characters.

There is a total of 74,074

characters.
Figs. 2 and 3 show the distribution of the length of the words versus
percentage of collection.

The abrupt end to the curves in Fig. 2 is due totruncation of words to 18 characters.
Both dictionaries have approximately the same size and proportionsof words of various length.
different.

B)

However, their vocabularies are considerably

A good hash scheme should work equally well on both dictionaries.

Hash Coding Algorithms

By their nature, hash coding algorithms are machine dependent.

The

computer representation of the alphabetic characters, the way in which arithmetic operations are done, and other factors all affect the randomness ofthe generated address.

The algorithms described below are intended for useon the IBM S/360.
Words are padded with some character to fill an integral number of
S/360 fullwords.

Then the fullwords are combined in some manner to form asingle fullword key, and the final hash address is computed from this key.
In the experiments which follow, the blank is used as a fill character.

Thisis an unfortunate choice because of the binary representation of the blank
01000000.

In some algorithms the zeroes may propagate or otherwise affectthe randomness.

A good fill character Is one that1)

is not available on a keypunch or teletype,2)

will not propagate zeroes,11-18O Common Words
A ADI
D CRAN 1400

8

10

12

14

Word Length

Distribution of Dictionary Words
According to Their Lengths
Fig. 2

11-19O Common Words
A ADI
D CRAN 1400

10

12

18

20

Word Length
Cumulative Distribution of Dictionary Words
According to Their Lengths
Fig. 3

11-203) will generate a few carries during key formation, andM-) has the majority of its bits equal to 0, so their positions
may be filled.
A likely candidate for the S/360 is 01000101.
Three basic methods of generating virtual hash addresses — addition,
multiplication, and division — are studied.

The first and second provide

contrasting ways of forming the single fullword keys.

The second and third

differ in the way the hash address is computed from the key. Variations ofeach basic method are also tested to try to improve speed, programming ease,or collision-storage properties.

1.

Addition Methods
AC — addition and center
The fullwords of characters are logically added to form the key.
The key is squared and the centermost bits are selected as the
major.

The minor is obtained from bits on both sides of the

major.
AS — addition with shifting
Same as AC, except the second, third, etc. full words are
shifted two positions to the left before their addition
in forming the key,

(An attempt to improve collision-storage

properties)
AM — addition with masking
Same as AC, except the second, third, etc. fullwords havecertain nonsignificant bits altered by masks before theiraddition in forming the key.

(An attempt to improve collision-storage properties)
2.

Multiplication Methods
MC — multiply and center
The fullwords of characters are multiplied together to form

11-21the key.

The center bits of the previous product are saved

as the multiplier for the next product.

The key is squared

and the centermost bits selected as the major.

The minor is

obtained from the bits on both sides of the major.
MSL — multiply and save left
Same as MC, but during formation of the key, the high order
bits of the products, rather than the center, are used as
successive multipliers.

CAn attempt to improve speed)

MLM — multiply with left major
Same as MC, but taking the major from the left half of thesquare of the key and the minor from the right half.

(Anattempt to improve speed)3.

Division Methods
DP — divide by prime
The fullwords of characters are multiplied together to form
the key.

The center bits of the previous product are saved

as the multiplier for the next product.

The key is divided

by the length of the virtual hash table — a prime number inthis case — and the remainder used as the virtual hash address.
The major is drawn from the left end of the virtual address
and the minor from the right.
DO — divide by odd number
Same as DP, except using a hash table whose length is odd.
(An attempt to provide more flexibility of hash table sizes)
DT — divide twice
Same as DP, except two divisions are made.

The major is

produced by dividing the key by the actual hash table size.
The minor results from a second division.
throughout as divisors.

Primes are used

CAn attempt to improve storage-

collision properties)C)

Evaluation

In the experiments to evaluate each variation of the above hash

11-22schemes, the size of the virtual hash table varies from 2 to 2 slots.
12m
The actual hash table varies in size from 2
to 2
slots. Bump table space
is used as needed.

The tables are filled by the words from either the ADI

or CRAN dictionaries and the collision and storage statistics taken. Because
good collision properties are most important, they are examined first. The
storage properties are dealt with later.
The number of collisions obtained from each scheme versus the virtualtable length is plotted in Figs. 4 to 7. The AD1 dictionary is shewn in Figs.
4 and 6, and the CRAN in Figs. 5 and 7.
curves

The circled lines correspond to

generated from equations C9) and Cl2). The horizontal one shows the

expected number of collisions and the lines above and below it enclose a
95% confidence interval about the expected curve.

In other words, if analgorithm is generating random addresses, the probability is 95% that the
curve for that scheme lies between the heavy lines.
Consider Figs. 4 and 5 showing the results for all the addition
methods and the MC variation of the multiplication variation.

The AC and

MC algorithms differ only in that addition is used in forming the key in thefirst one and multiplication in the second one. Yet the curves are spectacularly different.

The result seems to have the following explanation*

The purpose of a hash address computation is to generate a random
number from a string of characters.

If the bits in the characters are as

varied as possible, then the algorithm has a headstart in the right direction.
However, the S/360 bit patterns for the alphabet and numbers are:
A to 11100 xxxx

J to R

1101 xxxx

S to Z

1110 xxxx

0 to 91111 xxxx

11-23ooooo

Theoretical Curves(Equations (9) and (12))
Experimental Curves
Interpolated Curves

49

29

45

25

18

16

16

41

12

37

8

^C,AM33r

HAC,AM4hAS

29 |-ooooooooooooc7 "OOOOOOOOOOOO J— oooooooooo
000

O^ICjSSS^
25-£$

MC<*>°°o°'
21 kjo1"AS°o, ooooooooooooo
1C

8888888888 ° ^ C
26
28

24

0|
22

20
Virtual Hash Table Size (Power of two)

Collisions in the ADI Dictionary

for Addition

and Multiplication Hash Schemes

Fig.

4

ooooo58

Theoretical Curves(Equations (9) and (12))
Experimental Curves
Interpolated Curves

29

54

18

17

16

50

14

13

12

46

10

9

M&40
°o 0 ooooooooooooo
38

oooooooooy

oooooooooooo

jaoooooooooooo
Soooool

34

30
26
20
Virtual Hash Table Size

(Power of two)

Collisions in the CRAN Dictionary for
Addition and Multiplication Hash Schemes

Fig. 5

11-25ooooo

Theoretical Curves
Experimental Curves
Interpolated Curves

2 6 mo
22
18

16

16

14

12

12

8

8

DP
10

^"""•P--^

DO.

6h

at

DP

-O

z

DRi
°<5io5boooooooooooo.
DT-

fDO

DT

oooooooooooo2\-ooooQQQoqpoocmMCQ8SS88§§tiCt05\ MC.DP

T

I^JMCa^2-"^

26

25h

20
VirtualHash Table Size (Power of two)

Collisions in the ADI Dictionary for Division
and Multiplication Hash Schemes
Fig. 628

oooooTheoretical Curves(Equations (9) and (12))
Experimental Curves
Interpolated>ooCurves2l-oooooooooQfiPT^Toooooooooo^pjOPDT^MC

Virtual Hash Table Size

(Power of two)

Collisions in the CRAN Dictionary
and Multiplication
Fig. 7for Division

Hash Schemes11-27

In each case the two initial bits of a character are lTs so that in any
given word -r- of the bits are the same.
In forming a key, the successive additions in the AC algorithm may
obscure these nonrandom bits if sufficient number number of carries are
generated.

However, the number of additions performed is usually small —2 or 3 — and it appears that the patterns are not broken sufficiently. The
MC algorithm uses multiplication to form its keys which involves some 31
additions — certainly enough to make the resulting key random.
fThemultiplications ?*.n the MC algorithm are costly in terms of com-putation time.

Therefore the AS and AM algorithms are tried.

These addi-

tion variants try to hasten the breakup of the nonrandom bits by shiftingand masking respectively.

Although these variants reduce the number ofcollisions somewhat, none of the addition schemes could be called random.
Typically a few words are singled out at some point and continue to collide
regardless of the length of the virtual address.
are listed below.

Several collision pairs

Note the similarities between the words.
COUNT

-

SOUND

WORTH

-

FORTY

TOLERATED-TELEMETER

WHEEL

-

SHEET

Consider the multiplication algorithms.

During key formation, theprocess of saving the center of successive products adds to the computation
time.

The MSL variation attempts to remedy this by saving only the highorder bits between multiplications Con the S/360 this means saving theupper 32 bits of the 64 bit product).

This method is so inferior that its

collision graph could not be included with the others. The poor results

11-28stem from the fact that characters at the end of fullwords have little effecton the key and that the later multiplications swamped the effects of theearlier ones.

Examples of collision pairs are given below.

For convenience

the fullwords are separated by blanks.
CERT AINT Y -CERT AINL YPREV EKTE D -PRES ENTE DHEAV ING-

HEAT ING

EXPE NSE-

EXPA NSE

CHAR TER-CHAP TERI

The MC and MLM variants are identical with respect to collision properties.

In general these algorithms produce good results, reducing the num-

ber of collisions to zero in both dictionaries. The collision curve isalways beneath the expected one.
Consider Fig. 7 and 8 showing the results for all division methods
and the MC method.

All of the division algorithms display a distinct rise24m

the number of collisions when the virtual table size is near 2

less of the dictionary.

— regard-

The majority of the colliding word pairs are 4 char-acter words having the same two middle letters. This brings to light a curious fact about division algorithms.

For virtual tables, the divisor of the

key is large and the initial few bits determine the quotient, leaving therest for the remainder.

For words of less than 4 characters (which require24
no multiplications during key formation)> dividing by 2
is equivalent toselecting the last 3 characters of the word as the hash address. Because. .
24
the divisors are not exactly equal to 2 , only the two middle characterstend to be the same. Examples are:
DEAL

-

BEAR

11-29

TOOK

-

SOON

HELD

-

CELL

VERB

-

TERM

This phenomenon apparently continues for table sizes around 2

and28
2 , but there are few or no words of 4 characters or less which agree in
26 or 28 bits.

24
Eor divisors smaller than 2 , a larger part of the key

determines the quotient and apparently breaks up the pattern.
Because the above effect occurs only for

V = 2

24

, these points are

passed c^ver on the graphs.
In general, the DT algorithm is superior to the rest of the division
methods, mostly because each of its two divisors is smaller than those usedin other methods.

Prime numbers seem to produce better results than otherdivisors.
On the basis of collision properties, the MC, MLM, DT, and possibly
AS algorithms are the best.

Storage-search evaluations are included forthese methods only.
The experiments with each hash coding method also include counting
the frequency of various length of collision chains.

Here a collision

chain refers to chains of words producing the same major.

The frequency

counts are compared with the expected counts given by equation (5). The
comparison is in terms of a chi-square goodness of fit test with a 10% levelof significance.
dictionary.

Figs. 8 and 9 show the results of this test for each

Included in the graphs is the line corresponding to the 10%

level of significance.

If the major portions of the hash addresses arereally random, there is a probability of 0.90 that the 10% line will lie
above the curve for the algorithm tested.

AS.DT

MLM
MC-

_L
20

-MC-

22

-MC

-MC-

JL
24

26

Virtual Hash Table Size

28

(Power of two)

X —curve for 10% level of significanceDeviations ofValuesfor

Storage-Search Properties
Storage

Hash

from

Expected

Schemes using theDictionary

Fig. 8

ADI

MLM

MLM

_L
20

22

J_
24

J_
26

28

Virtual Hash Table Size (Power of two)
X —curve for 10% level of significanceDeviations of Storage —Search Properties from Expected
Values for Selected Hash Schemes using the CRAN
Dictionary
Fig. 911-32

Consider the MC and MLM algorithms which differ only in that the
major is selected from the center and left of the virtual address. Fromthe graphs, it is clear that the multiplication methods produce their mos":random bits in the center of their product. This is somewhat as expected
because the center bits are involved in more additions than other bits.
The division algorithm, which had fairly good collision properties,
seems to have rather mediocre storage properties. This is probably due tothe same causes as the collision problems, but working at a lower level, andnot affecting the results as much.
The AS curve is included simply for completeness. The scheme displays a well behaved storage curve, but unfortunately it has poor collision
properties.
In summary, the MC scheme seems to be the best for both dictionaries
in terms of collision and search properties.

In terms of computing time,the method is more time consuming than the addition methods, but less expensive than the division methods. The differences in computation times is
not an extremely big factor.

All methods required from 35 to 55 microseconds

for an 8 character word on the S/360/65.

The routines are coded in assembly

language and called from a Fortran executive. The times above include thenecessary bookkeeping for linkage between the routines.

5.

A Practical Lookup SchemeA) General Description
The lookup scheme described below is designed for use with dictionaries

1529
of about 2 v words. The virtual table size selected is 2 ' and the actual
15table size is 2 . On the basis of the results presented in previous sections,11-33

when the dictionary is full, it is expected that1)

36.8% of the hash table will be empty,

2)36.8% of the hash table will be single entries,

153) the bump table will require (0.632)2 v e n t r i e s ,*+) 1 collision is e x p e c t e d ,5) the probability of 5 or fewer collisions is 0.999, and6) the average lookup will require 2.13 probes.
(B)

Table Layout

In all previous discussions a dictionary entry has included a minor
and a concept number. A concept number is simply a unique number assigned
to each word.
used.

The hash address of a word is also unique, and hence can be

There is no need to store and use a previously assigned concept num-ber.
A dictionary entry contains a 14 bit minor and a single bit indicating whether the word is common or noncommon;

1

2

15
Minor

C = 0

implies the word is common

C = 1

implies the word is noncommon.

A hash table entry contains 16 bits arranged as:

0
Flag

lb

1
Information

Flag = 0

implies that the information is a dictionaryentry

11-34

Flag = 1

implies that the information is a pointer tothe bump table

Words that have the same major are stored in a block of consecutive
locations in the bump table. This eliminates the need for pointers in thecollision "chains". A bump table entry also has 16 bits structured as:

1

0

1

End

C

2

15
Minor
1

End = 0

.

•

.

•

•

•

•

,

.

.

•

„

|

•

.

„

•

•

•

implies that the entry is not the last in
the collision block

End = 1

implies that the entry is the last in theblock.

Some convention must be adopted to signify an empty hash table slot. A
zero is most convenient in the above scheme. Unfortunately a zero is alsoa legitimate minor.

However, to cause trouble the word generating the zerominor would have to be a common word and a single table entry (zero minors
in the bump table are no problem).

Hopefully this occurs rarely because of

the size of the minor (14 bits) and the small number of common words. However, even if this combination of circumstances occurs, the common word
could be placed in the bump table anyway.
In designing the tables, it is important to make the hash table
entries large enough to accommodate the largest pointer anticipated for thebump table.
2

For the above scheme, the expected bump table size is less thanso that the 15 bits allocated for pointers is sufficient.
C) Search Considerations
The number of probes needed to locate any given word depends on the11-35place that the word occupies in a collision block.

The average search timeis improved if the most common words occupy the initial slots in each block,A study of ADI text yields the following statistics.

Division of Words by Category
Number of Words

Percent of Total

17270 Total words

100.0

8716 Common words

50.5

8554 Noncommon words

49.5

Distribution of Lengths
Number ofCharacters

All
Words

Percent

Common
Words

Percent

1-4

10145

58.8

8057

92.5

2097

24.5

5-8

4630

26.8

627

7.2

4003

46.8

9-12

2249

13,0

32

0.3

2217

25.9

13-16

221

1.3

0

0.0

221

2.6

17-20

11

0.1

a

0.0

11

0..1

21-24

5

a. a

0

0.0

5

0.1

Totals

17270

100,0

8716

100.0-

8554

100.0

Average
Length6.3

4.3

Noncommon
Words

Percent

8.3

Using the categorical information, it appears that in filling the hash-bumptables, the common words should be entered first. Within each category,
all words should be entered in frequency order if such information is known,
If frequency information is not available, the distribution by lengths can

11-36be used as an approximation to it. For common words, this means entering
the shorter words first.

For noncommon words, the words of 5 to 8 charac-ters should be entered first.
The greater the number of single entries, the greater the average
search speed.

Fig. 1Q shows the fraction of single entries (J,) and frac-tion of empty slots (J ) for various load factors. The fraction of single
entries

F

—ot
= ae
reaches a maximum for

a = 1, but since the slope ofthe curve is small around this point, and load factor in the interval CD.8,
1.2) is practically the same. Table usage is better, however, for the larger values ofa.

These facts imply that scatter storage schemes make mostefficient use of space and time fora = 1.

Most text words can be assumed to be in the dictionary.
order of comparisons during lookup should be:
Hash Table Scan1) check minor assuming the text word is a common word2) check minor assuming the word is noncommon
3) check if the entry is a pointer to the bump table4) check if the entry is empty
First Bump Table Entry Cmust be at least two)5) check minor assuming the word is a common word6) check minor assuming the word is noncommon
Other Bump Table Entries7) check minor assuming the word is noncommon
8) check minor assuming the word is common
9) check if at end of collision block.

Thus the11-37

.70

60

P
o
X

O

FractionA

Fraction of Single Entries

50

.40

A"
c
o
a
o

/

.30

/
.20

ioh

.8

1.2

1.6

2.0

Load Factor

Theoretical

Hash

Table

F i g . 10

Usage

Empty

Slots

11-38The search pattern can be varied to take advantage of the storage conditions.
For example, if all common words are either single entries or the firstelement of a collision block, then step 8) may be eliminated.

D) Performance
The lookup system described above has been implemented and testedon the IBM S/360/65.

A modified form of the MC algorithm is used to com-pute a 29 bit virtual address and divide it into a 15 bit major and a 14bit minor.

The modification is the inclusion of a single left shift of

the fullwordi of characters during key formation. This breaks up certain
types of symmetries between words such as WINGTAIL and TAILWING. Without
this, such words will always collide. The hash-bump tables were filledwith entries from the ADI dictionary — common words first, followed bynoncommon words. The shortest words were entered first. A comparison of
the expected and actual results follows.

a = .239

Expected

ActualNumber of empty table slots

25810

25762

Number of single entries

6161

6250

Number of collision blocks

797

756

Longest collision block4

4

Average length of collision
blocks2.1

2,1Size of bump table
Number of collisions
Average probes per lookup

1572

16-63
.06
1.33

1.33

11-39To obtain the actual lookup times 627 words were processed.
words were read from cards and all punctuation removed.

The

Each word waspassed to the lookup program as a continuous string of characters with theproper number of fill characters added.

The resulting times are given

below (in microseconds):

Categoryof Words

Numberof Words

Percentof Total

AverageTime

Standard
Deviation

Average
Probes

All v

627

100.0

57.9

11.7

1.18

Common

288

45.9

49.9

6.7

1.12

Noncommon

338

53.9

64.7

10.7

1.24

Not found*

1

0.2

53.1

0.0

1.00

* A larger sample with less accurate timings indicates that the averagetime for words in this category is about 62 microseconds (standard
deviation 26).

The time to compute a hash address depends on the length of the
word.

Let

acters.

nbe the number of S/360 fullwords needed to hold these char-

The time to form the initial address isI(n) = 34.5 + 10.2 (n - 1)

microseconds.

The average total lookup time, then, is

T = I(n) + cP

where

c

is the average time per probe into the table space andP

is theaverage number of probes.

For the words in the experimentI(n) = 40.3, andso that each probe required about 15 microsec-

onds.

T = 57.9

n = 2.3 2 (average),

11-40E)

Comparisons

Timing information for other lookup schemes is difficult to obtain.
A tree structured dictionary is used for a similar purpose at Harvard.

Pub-

lished information indicates 6pq microseconds are needed to process

words

in a dictionary ofqentries.

This time is for the IBM 709*4.

p

Translating

this time to the S/360/65, which is roughly 4 times faster, and using the
ADI dictionary (q = 7822), it appears that each lookup averages 11,000 microseconds.

Exactly how much computation and input-output this includes is

unknown.

6.

Extensions
A)

Larger Dictionaries

As more words are added to the dictionary, the size of the virtual
address must increase in order to prevent collisions.

As a result, the num-

ber of bits per table slot must also increase in order to accommodate thelarger minors and pointers that are used.

For a fixed sized hash table, thenumber of entries in the bump table grows as new words are added.

At somepoint the space required for tables will exceed the amount of core allottedfor dictionary use.

To salvage the scheme, it may be possible to split thebump table into parts — one part for more frequently used words and one forwords in rather rare usage.

During dictionary construction common words

are entered first, then noncommon, then rare.

When a rare word must beplaced in a collision block, a marker is stored instead, and the item isplaced in the secondary bump table.

Presumably the nature of the words

in the second bump table will make its usage rather infrequent, thus saving
accesses to auxiliary storage to fetch it.

11-41

B)

Suffix Removal

Many dictionary schemes store only word stems; the lookup attempts
to match only the stem, disregarding suffixes in the process.
easily done with scatter storage schemes.

This is not

One solution is to try to remove

the suffix after an initial search has failed.

Each of the various possi-

ble stems must be looked up independently until a match is found.

Anothersolution is to use a table of correspondences between the various forms ofa word and its stem.

The concept number could be used as an index on thistable containing pointers to information about the actual stem.

A thesaurus

lookup can be handled the same way.

7.

Conclusions
Virtual scatter storage schemes are well suited for dictionaries,

having both rapid lookup and economy of storage.

The rapid lookup is dueto the fact that the initial table probe limits the search to only a few
items.

The space savings come from the fact that the actual character

strings for words are not part of the dictionary.

The schemes depend

heavily on a good algorithm for producing random hash addresses.

The

theory developed in Sections 2 and 3 gives a basis for judging the worthof proposed algorithms.
For any particular application, the table organization may vary
to suit different needs and to store different information.
advantages of scatter storage schemes are still present.

However, theReferences[1]

Salton, G.f A document retrieval system for man-machine interaction, Association for Computing Machinery, Proceedings of the
19th National Conference, Philadelphia, Pennsylvania, August 25-27,
1964, pp. L2.3-1 — L2.3-20.

[2]Mcllroy, M. D., Dynamic Storage Allocation, unpublished manuscript,
Bell Telephone Laboratories, Inc., 1965.

[3]

Morris, R., "Scatter Storage Techniques", Communications of theACM, January, 1968.

[4]

Maurer, W. D., "An Improved Hash Code for Scatter Storage",
Communications of the ACM, January, 1968.

{5J

Johnson, L. R., "Indirect Chaining Method for Addressing on
Secondary Keys", Communications of the ACM, May 1961.