Four
FILE STRUCTURES

Introduction
This chapter is mainly concerned with the way in which file structures
are used in document retrieval. Most surveys of file structures address
themselves to applications in data management which is reflected in theterminology used to describe the basic concepts. I shall (on the whole)follow Hsiao and Harary1 whose terminology is perhaps slightly
non-standard but emphasises the logical nature of file structures. A
further advantage is that it enables me to bridge the gap between data
management and document retrieval easily. A few other goodreferences on file structures are Roberts2, Bertziss3, Dodd4, andClimenson5.
Basic terminology
Given a set of ‘attributes’ A and a set of ‘values’ V, then a record R is asubset of the cartesian product A x V in which each attribute has one
and only one value. Thus R is a set of ordered pairs of the form (anattribute, its value). For example, the record for a document which has
been processed by an automatic content analysis algorithm would be

The K{’s are keywords functioning as attributes and the value x,- can bethought of as a numerical weight. Frequently documents are simply
characterised by the absence or presence of keywords, in which case wewrite
R = { K tl, K h , . . . , K t.}
where K ti is present if x tj = 1 and is absent otherwise.
56

FILE STRUCTURES

Records are collected into logical units called files. They enable one
to refer to a set ,of records by name, the file name. The records within afile are often organised according to relationships between the records.
This logical organisation has become known as a file structure (or data
structure).
It is difficult in describing file structures to keep the logical features
separate from the physical ones. The latter are characteristics forced
upon us by the recording media (e.g. tape, disk). Some features can be
defined abstractly (with little gain) but are more easily understoodwhen illustrated concretely. One such feature is a field. In any
implementation of a record, the attribute values are usually positional,
that is the identity of an attribute is given by the position of its
attribute value within the record. Therefore the data within a record isregistered sequentially and has a definite beginning and end. The record
is said to be divided into fields and the wth field carries the «thattribute value. Pictorially we have an example of a record withassociated fields in Figure 4.1.

k 2

*1

*3

Ku

P^

Pi

Pi

Pt

Figure 4.1. An example o f a record with associated fields

The fields are not necessarily constant in length. To find the value ofthe attribute K4, we first find the address of the record R (which isactually the address of the start of the record) and read the data in the
4th field.
In the same picture I have also shown some fields labelled Pf. They
are addresses of other records, and are commonly called pointers. Now
we have extended the definition of a record to a set of attribute-value
pairs and pointers. Each pointer is usually associated with a particular
57 '
IR-S

FILE STRUCTURES

attribute-value pair. For example, (see Figure 4.2) pointers could be
used to link all records for which the value x x (of attribute K t ) is a,similarly for x 2 equal to b, etc.

Figure 4.2. A demonstration o f the use o f pointers to link records

To indicate that a record is the last record pointed to in a list ofrecords we use the null pointer A . The pointer associated with attribute
K in record R will be called a K-pointer. An attribute (keyword) that isused in this way to organise a file is called a key.
To unify the discussion of file structures we need some further
concepts. Following Hsiao and Harary again, we define a list L ofrecords with respect to a keyword.A, or more briefly a K-list as a set ofrecords containing K such that;( 1 ) the A-pointers are distinct;(2) each non-null /f-pointer in L gives the address of a record withinL;(3) there is a unique record in L not pointed to by any record
containing K; it is called the beginning of the list; and(4) there is a unique record in L containing the null A-pointer; it isthe end of the list.
(Hsiao and Harary state condition (2) slightly differently so that no two/f-lists have a record in common; this only appears to complicate
things.)From our previous example:
K i —list : R \, R 3, R 5
A 2—list : R 2, R 4^ 4—lis t: R \, R 2, R 3
Finally, we need the definition of a directory of a file. Let F be a filewhose records contain just m different keywords K x, K 2l . . . , Km . Let
be the number of records containing the keyword Kh and ht be the58FILE STRUCTURES

number of A,-lists in F. Furthermore, we denote by a(y the beginning
address of the /th A,-list. Then the directory is the set of sequences(A,-, rij, hi, an , an , . . . aih)i= 1, 2, . . . m

We are now in a position to give a unified treatment of sequential
files, inverted files, index-sequential files and multi-list files.
Sequential files
A sequential file is the most primitive of all file structures. It has nodirectory and no linking pointers. The records are generally organised inlexicographic order on the value of some key. In other words, aparticular attribute is chosen whose value will determine the order ofthe records. Sometimes when the attribute value is constant for a large
number of records a second key is chosen to give an order when thefirst key fails to discriminate.
The implementation of this file structure requires the use of asorting routine.
Its main advantages are:( 1) it is easy to implement;( 2) it provides fast access to the next record using lexicographic
order.
Its disadvantages:( 1) it is difficult to update — inserting a new record may require
moving a large proportion of the file;( 2) random access is extremely slow.
Sometimes a file is considered to be sequentially organised despite
the fact that it is not ordered according to any key. Perhaps the date ofacquisition is considered to be the key value, the newest entries areadded to the end of the file.
Inverted files
The importance of this file structure will become more apparent when
Boolean Searches are discussed in the next chapter. For the moment welimit ourselves to describing its structure.
An inverted file is a file structure in which every list contains only
one record. Remember that a list is defined with respect to a keyword
K, so every AT-list contains only one record. This implies that thedirectory will be such thatfor all i, that is, the number ofrecords containing A,- will equal the number of A',-lists. So the directory
59

FILE STRUCTURES

will have an address for each record containing Kt. For document
retrieval this means that given a keyword we can immediately locate theaddresses of all the documents containing that keyword. For theprevious example let us assume that a non-blank entry in the fieldcorresponding to an attribute indicates the presence of a keyword and ablank entry its absence. Then the directory will point to the file in theway shown in Figure 4.3. The definition of an inverted file does not
F ile,3 ,3 ,0 ,, , 0 , 2 , 0,33,2,03,, O2 2\

k'i ,3 ,3 ,o t l ,o 42,o 4:

Figure 4.3. An inverted filerequire that the addresses in the directory are in any order. However, tofacilitate operations such as conjunction (‘and’) and disjunction (‘or’)on any two inverted lists, the addresses are normally kept in record
number order. This means that ‘and’ and ‘or’ operations can be
performed with one pass through both lists. The penalty we pay is ofcourse that the inverted file becomes slower to update.
Index-sequential files
An index-sequential file is an inverted file in which for every keyword
Kt, we have nt =hi = 1 a n d au < a 2 i- ■ am l . This situation can only
arise if each record has just one unique keyword, or one unique
60

FILE STRUCTURES

attribute-value. In practice therefore, this set of records may be orderedsequentially by a key. Each key value appears in the directory with theassociated address of its record. An obvious interpretation of a key ofthis kind would be the record number. In our example none of theattributes would do the job except the record number.
Diagrammatically the index-sequential file would therefore appear as
shown in Figure 4.4. I have deliberately written R ( instead of Kt toemphasise the nature of the key.
File

Figure 4.4. An index-sequential file61

FILE STRUCTURESIn the literature an index-sequential file is usually thought of as asequential file with a hierarchy of indices. This does not contradict theprevious definition, it merely describes the way in which the directory
is implemented. It is not surprising therefore that the indexes
C ylinder and track
containing index

M a s te r index[C o re s to re ]—•C ylinder index[C ylin d er 1,
track 010]

Track index[C y lin d e r 1,
track 0 3 0 ]D ata a rea

1/01 00150

2 /0 2 00250

3 /0 1 50350

H ighest key referenced
for corresponding index—•

Highest key referenced
for corresponding index

Track ad d re s s ofrecord index

0050

015

0150

030

H ighest key in track
,

Track

S tart of track

0080

090

00100

091

Key

D ata

0060
0065
090

091

0070
0080
0085
0090
0095
0100

Figure 4.5. An example o f an implementation o f an index-sequential file (Adaptedfrom D. R. Judd, The Use of Files, Macdonald and Elsevier, London and New
York, 1973, page 46)62

FILE STRUCTURES(‘index’ = ‘directory’ here) are often oriented to the characteristics ofthe storage medium. For example (see Figure 4.5) there might be threelevels of indexing: track, cylinder and master. Each entry in the trackindex will contain enough information to locate the start of the track,and the key of the last record in the track, which is also normally thehighest value on that track. There is a track index for each cylinder.
Each entry in the cylinder index gives the last record on each cylinder
and the address of the track index for that cylinder. If the cylinderindex itself is stored on tracks, then the master index will give thehighest key referenced for each track of the cylinder index and thestarting address of that track.
No mention has been made of the possibility of overflow during an
updating process. Normally provision is made in the directory toadminister an overflow area. This of course increases the number ofbook-keeping entries in each entry of the index.
Multi-lists
A multi-list is really only a slightly modified inverted file. There is one
list p er keyword, i.e. h{ = 1. The records containing a particular
keyword A, are chained together to form the Ar list and the start of theA,-list is given in the directory, as illustrated in Figure 4.6. Since there
is no A 3-list the field reserved for its pointer could well have been
omitted. So could any blank pointer field, so long as no ambiguity
arises as to which pointer belongs to which keyword. One way ofensuring this, particularly if the data values (attribute-values) are fixed
format, is to have the pointer not pointing to the beginning of therecord but pointing to the location of the ne'xt pointer in the chain.
The multi-list is designed to overcome the difficulties of updating an
inverted file. The addresses in the directory of an inverted file arenormally kept in record-number order. But, when the time comes to
add a new record to the file, this sequence must be maintained, andinserting the new address can be expensive. No such problem arises withthe multi-list, we update the appropriate A-lists by simply chaining in
the new record. The penalty we pay for this is of course the increase in
search time. This is in fact typical of many of the file structures.
Inherent in their design is a trade-off between search time and update
time.
Cellular multi-lists
A further modification of the multi-list is inspired by the fact thatmany storage media are divided into pages, which can be retrieved one
63

FILE STRUCTURES

Figure 4.6. A multi-listat a time. A X'-list may cross several page boundaries which means thatseveral pages may have to be accessed to retrieve one record. A
modified multi-list structure which avoids this is called a cellular
multi-list. The X'-lists are limited so that they will not cross the page(cell) boundaries.
At this point the full power of the notation introduced before
comes into play. The directory for a cellular multi-list will be the set ofsequences(K 0 nit hi, a n , . . . , aih.) i = l , 2 , . . . , m
64

FILE STRUCTURES

where the hj have been picked to ensure that a A,-list does not cross apage boundary. In an implementation, just as in the implementation of
an index-sequential file, further information will be stored with eachaddress to enable the right page to be located for each key value.

Ring structures
A ring is simply a linear list that closes upon itself. In terms of thedefinition of a A-list, the beginning and end of the list are the same
record. This data-structure is particularly useful to show classificationof data.
Let us suppose that a set of documents{D\, D 2, D 3, £>4, D$, Dg, D 2, Dg}
has been classified into four groups, that is{(£>1, D 2), (D3, £>4), (Ds, D 6), (Dn, Dg)}
Furthermore these have themselves been classified into two groups,{((Du D 2), (D3, £>4)), ((Dg, D 6), (Dn, Dg))}

D1

02

Dj

D4

D5

Ds

07

Ds

Figure 4.1. A dendrogram

The dendrogram for this structure would be that given in Figure 4.7. To
represent this in storage by means of ring structures is now a simple
matter (see Figure 4.8).
The Dj indicates a description (representation) of a document.
Notice how the rings at a lower level are contained in those at a higher
level. The field marked Cj- normally contains some identifying
information with respect to the ring it subsumes. For example, C\ insome way identifies the class of documents {Dx, D 2 }•65

FILE STRUCTURES

Figure 4.8. An implementation o f a dendrogram via ring structures

Were we to group documents according to the keywords theyshared, then for each keyword we would have a group of documents,
namely, those which had that keyword in common. C) would then be
the field containing the keyword uniting that particular group. The
rings would of course overlap {Figure 4.9), as in this example:
D x = { K „ K 1\
D 2 ={K 2 , K 3}
D 3 ={ K u K 4 }Figure 4.9. Two overlapping rings

66

FILE STRUCTURESThe usefulness of this kind of structure will become more apparent
when we discuss searching of classifications. If each ring has associatedwith it a record which contains identifying information for its
members, then, a search strategy searching a structure such as this will
first look at C, (or Kj in the second example) to determine whether toproceed or abandon the search.

Threaded lists

In this section an elementary knowledge of list processing will beassumed. Readers who are unfamiliar with this topic should consult thelittle book by Foster6.
A simple list representation of the classification((D 1, D 2), (D3, D , ) l ((Ds, De), {Dlt D 8))

is given in Figure 4.10. Each sublist in this structure has associated withit a record containing only two pointers. (We can assume that £>, isreally a pointer to document £),-.) The function of the pointers should
be clear from the diagram. The main thing to note, however, is that therecord associated with a list does not contain any identifying
information.

Figure 4.10. A list structure implementation o f a hierarchic classification

A modification of the implementation of a list structure like thiswhich makes it resemble a set of ring structures is to make the righthand pointer of the last element of a sublist point back to the head of67

FILE STRUCTURES

Figure 4.11. A threaded list implementation o f a hierarchic classification

the sublist. Each sublist has become effectively a ring structure. We now
have what is commonly called a threaded list (see Figure 4.11). The
representation I have given is a slight oversimplification in that we needto flag which elements are data elements (giving access to the
documents £),•) and which elements are just pointer elements. The majoradvantage associated with a threaded list is that it can be traversed
without the aid of a stack. Normally when traversing a conventional list
structure the return addresses are stacked, whereas in the threaded list
they have been incorporated in the data structure.
One disadvantage associated with the use of list and ring structures
for representing classifications is that they can only be entered at the‘top’. An additional index giving entry to the structure at each of thedata elements increases the update speed considerably.
Another modification of the simple list representation has beenstudied extensively by Stanfel7,8 and Patt9. The individual elements(or cells) of the list structure are modified to incorporate one extra
field, so that instead of each element looking like this
it now looks like thiswhere the P /s are pointers and S is a symbol. Otherwise no essentialchange has been made to the simple representation. This structure has
become known as the Doubly Chained Tree. Its properties have mainly
been investigated for storing variable length keys, where each key ismade up by selecting symbols from a finite (usually small) alphabet.
68

FILE STRUCTURES

For example, let {A,B,C}be the set of key symbols and let R \, R 2, R 3 ,R 4, R s be five records to be stored. Let us assign keys made of the 3
symbols, to the records as follows:
AAA
R
AB

R

AC

R

BB

R.

R
BC
An example of a doubly chained tree containing the keys and giving
access to the records is given in Figure 4.12. The topmost element
contains no symbol, it merely functions as the start of the structure.
Given an arbitrary key its presence or absence is detected by matching

Level 0Level 1

Level 2

Level 3Figure 4.12. An example o f a doubly chained tree

it against keys in the structure. Matching proceeds level by level, once amatching symbol has been found at one level, the P 1 pointer isfollowed to the set of alternative symbols at the next level down. The
matching will terminate either:( 1) when the key is exhausted, that is, no more key symbols are left
to match; or( 2) when no matching symbol is found at the current level.
69

FILE STRUCTURES

For case (1) we have:(a) the key is present if the Pi pointer in the sa'me cell as the lastmatching symbol now points to a record;(b) Pi points to a further symbol, that is, the key ‘falls short’ and istherefore not in the structure.
For case (2), we also have that the key is not in the structure, but now
there is a mismatch.
Stanfel and Patt have concentrated on generating search trees withminimum expected search time, and preserving this property despite
updating. For the detailed mathematics demonstrating that this ispossible the reader is referred to their cited work.

Trees

Although computer scientists have adopted trees as file structures, theirproperties were originally investigated by mathematicians. In fact a
substantial part of the Theory o f Graphs is devoted to the study oftrees. Excellent books on the mathematical aspects of trees (andgraphs) have been written by Berge10, Harary et a /.,11 and Ore12.
Harary’s book also contains a useful glossary of concepts in graphtheory. In addition Bertziss3 and Knuth 13 discuss topics in graphtheory with applications in information processing.
There are numerous definitions of trees. I have chosen a particularly
simple one from Berge. If we think of a graph as a set of nodes (orpoints or vertices) and a set of lines (or edges) such that each line
connects exactly two nodes, then a tree is defined to be a finite
connected graph with no cycles, and possessing at least two nodes. To
define a cycle we first define a chain. We represent the line unjoining
two nodes x and y by u k = [x,y]. A chain is a sequence of lines, inwhich each line u k has one node in common with the preceding line
uk_ x, and the other vertex in common with the succeeding line uk+l.
An example of a chain is \a,x i ] , [*i ,x 2 ] , [x2 ,x 3 ] , [x 3,h ] . A cycle is a
finite chain which begins at a node and terminates at the same node(i.e. in the example a = b).
Berge gives the following theorem showing many equivalentcharacterisations of trees.
Theorem. Let H be a graph with at least n nodes, where n > 1; any
one of the following equivalent properties characterises a tree.
( 1) //is connected and does not possess any cycles.
(2) H contains no cycles and has n — 1 lines.
(3) H is connected and has n — 1 lines.
70

FILE STRUCTURES(4) H is connected but loses this property if any line is deleted.
(5) Every pair of nodes is connected by one and only one chain.
One thing to be noticed in the discussion so far is that no mention
has been made of a direction associated with a line. In mostapplications in computer science (and IR) one node is singled out as
special. This node is normally called the root of the tree, and every
other node in the tree can only be reached by starting at the root andproceeding along a chain of lines until the node sought is reached.
Implicitly therefore, a direction is associated with each line. In fact,
when one comes to represent a tree inside a computer by a list
structure, often the addresses are stored in a way which allows
movement in only one direction. It is convenient to think of a tree as adirected graph with a reserved node as the root of the tree. Of course, if
one has a root then each path (directed chain) starting at the root will
eventually terminate at a particular node from which no further
branches emerge. These nodes are called the terminal nodes of the tree.
By now it is perhaps apparent that when we were talking about ring
structures and threaded lists in some of our examples we were reallydemonstrating how to implement a tree structure. The dendrogram in
Figure 4.7 can easily be represented as a tree {Figure 4.13). The
documents are stored at the terminal nodes and each node represents aclass (cluster) of documents. A search for a particular set of documents
would be initiated at the root and would proceed along the arrows until
the required class was found.

Top of tree.# Root

D:

D2

O3

D§

Dg

Dy

Dt

Terminal nodes

Bottomof treeFigure 4.13. A tree representation o f a dendrogram71

FILE STRUCTURES

Another example of a tree structure is the directory associated withan index-sequential file. It was described as a hierarchy of indexes, but
could equally well have been described as a tree structure.
The use of tree structures in computer science dates back to theearly 1950s when it was realised that the so-called binary search could
readily be represented by a binary tree. A binary tree is one in which
each node (except the terminal nodes) has exactly two branches leaving
it. A binary search is an efficient method for detecting the presence orabsence of a key value among a set of keys. It presupposes that the keys
have been sorted. It proceeds by successive division of the set, at eachdivision discarding half the current set as not containing the sought key.
When the set contains N sorted keys the search time is of order logjA.
Furthermore, after some thought one can see how this process can be
simply represented by a binary tree.
Unfortunately, in many applications one wants the ability to insert a
key which has been found to be absent. If the keys are stored
sequentially then the time taken by the insertion operation may be oforder A. If one, however, stores the keys in a binary tree this lengthy
insert time may be overcome, both search and insert time will be oforder log2A. The keys are stored at the nodes, at each node a left
branch will lead to ‘smaller’ keys, a right branch will lead to ‘greater’keys. A search terminating on a terminal node will indicate that the key
is not present and will need to be inserted.
The structure of the tree as it grows is largely dependent on theorder in which new keys are presented. Search time may become
unnecessarily long because of the lop-sidedness of the tree. Fortunately,
it can be shown (Knuth14) that random insertions do not change theexpected log2A' time dependence of the tree search. Nevertheless,methods are available to prevent the possibility of degenerate trees.
These are trees in which the keys are stored in such a way that the
expected search time is far from optimal. For example, if the keys wereto arrive for insertion already ordered then the tree to be built would
simply be as shown in Figure 4.14.
It would take us too far afield for me to explain the techniques foravoiding degenerate trees. Essentially, the binary tree is maintained insuch a way that at any node the subtree on the left branch has
approximately as many levels as the subtree on the right branch. Hencethe name balanced tree for such a tree. The search paths in a balanced
tree will never be more than 45 per cent longer than the optimum. The
expected search and insert times are still of order log A. For further
details the reader is recommended to consult Knuth14.
So far we have assumed that each key was equally likely as a searchargument. If one has data giving the probability that the searchargument is Kt (a key already in the tree), and the probability that the72

FILE STRUCTURES

Figure 4.14. An example o f a degenerate tree

search argument lies between K{ and Ki+1, then again techniques are
known for reordering the tree to optimise the expected search time.
Essentially one makes sure that the more frequently accessed keys havethe shortest search paths from the root. One well-known techniqueused when only the second set of probabilities is known, and the others
assigned the value zero, is the Hu-Tucker algorithm. Again theinterested reader may consult Knuth.
At this point it is probably a good idea to point out that these
efficiency considerations are largely irrelevant when it comes torepresenting a document classification by a tree structure. The situationin document retrieval is different in the following aspects:( 1) we do not have a useful linear ordering on the documents;( 2) a search request normally does not seek the absence or presenceof a document.
In fact, what we do have is that documents are more or less similar toeach other, and a request seeks documents which in some way best
match the request. A tree structure representing a documentclassification is therefore chosen so that similar documents may beclose together. Therefore to rearrange a tree structure to satisfy some‘balancedness’ criterion is out of the question. The search efficiency isachieved by bringing together documents which are likely to berequired together.
This is not to say that the above efficiency considerations areunimportant in the general context of IR. Many operations, such as thesearching of a dictionary, and using a suffix stripping algorithm can bemade very efficient by appropriately structuring the binary tree.
73

FILE STRUCTURES

The discussion so far has been limited to binary trees. In many
applications this two-way split is inappropriate. The natural way torepresent document classifications is by a general tree structure, where
there is no restriction on the 1 number of branches leaving a node.
Another example is the directory of an index sequential file which isnormally represented by an m -way tree, where m is the number ofbranches leaving a node.
Finally, more comments are in order about the manipulation of tree
structures in mass storage devices. Up to now we have assumed that tofollow a set of pointers poses no particular problems with regard to
retrieval speed. Unfortunately, present random access devices are
sufficiently slow for it to be impossible to allow an access for, say, eachnode in a tree. There are ways of partitioning trees in such a way thatthe number of disk accesses during a tree search can be reduced.
Essentially, it involves storing a number of nodes together in one ‘page’of disk storage. During a disk access this page is brought into fast
memory, is then searched, and the next page to be accessed isdetermined.

Scatter storage or hash addressing

One file structure which does not relate very well to the ones
mentioned before is known as Scatter Storage. The technique by which
the file structure is implemented is often called Hash Addressing. Its
underlying principle is appealingly simple. Given that we may access thedata through a number of keys Kit then the address of the data in store
is located through a key transformation function / which when applied
to Kj evaluates to give the address of the associated data. We areassuming here that with each key is associated only one data item. Also
for convenience we will assume that each record (data and key) fits into
one location, whose address is in the image space of /. The addresses
given by the application of f to the keys Kt are called the hash addresses
and / is called a hashing function. Ideally / should be such that it
spreads the hash addresses uniformly over the available storage. Of
course this would be achieved if the function were one-to-one.
Unfortunately this cannot be so because the range of possible key
values is usually considerably larger than the range of the available
storage addresses. Therefore, given any hashing function we have tocontend with the fact that two distinct keys Kt and Kj are likely to map
to the same address fiKf) (=f(Kj)). Before I explain some of the ways ofdealing with this I shall give a few examples of hashing functions.
74

FILE STRUCTURES

Let us assume that the available storage is of size 2m then three
simple transformations are as follows:«( 1) if Kj is the key, then take the square of its binary representationand select m bits from the middle of the result;( 2) cut the binary representation of Kt into pieces each of m bits
and add these together. Now select the m least significant bits ofthe sum as the hash address;(3) divide the integer corresponding to Kt by the length of theavailable store 2 m and use the remainder as the hash address.
Each of these methods has disadvantages. For example, the last one
may give the same address rather frequently if there are patterns in the
keys. Before using a particular method the reader is advised to consult
the now extensive literature on the subject, e.g. Morrisls, or Lum etal.16.
As mentioned before there is the problem of collisions, that is, when
two distinct keys hash to the same address. The first point to be madeabout this problem is that it destroys some of the simplicity of hashing.
Initially it may have been thought that the key need not be stored withthe data at the hash address. Unfortunately this is not so. No matter
what method we use to resolve collisions we still need to store the key
with the data so that at search time when a key is hashed we candistinguish its data from the data associated with keys which have
hashed to the same address.
There are a number of strategies for dealing with collisions.
Essentially they fall into two classes, those which use pointers to link
together collided keys and those which do not. Let us first look at theones which do not use pointers. These have a mechanism for searching
the store, starting at the address where the collision occurred, for an
empty storage location if a record needs to be inserted, or, for amatching key value at retrieval time. The simplest of these advancesfrom the hash address each time moving along a fixed number oflocations, say s, until an empty location or the matching key value isfound. The collision strategy thus traces out a well defined sequence oflocations. This method of dealing with collisions is called the linear
method. The tendency with this method is to store collided records as
closely to the initial hash address as possible. This leads to an
undesirable effect called primary clustering. In this context all thismeans is that the records tend to concentrate in groups or bunch-up. It
destroys the uniform nature of the hashing function. To be more
precise, it is desirable that hash addresses are equally likely, however,the first empty location at the end of a collision sequence increases inlikelihood in proportion to the number of records in the collision
sequence. To see this one needs only to realise that a key hashed to any
75FILE STRUCTURES

location in the sequence will have its record stored at the end of thesequence. Therefore big groups of records tend to grow even bigger:
This phenomenon is aggravated by a small step size s when seeking an
empty location. Sometimes s = 1 is used in which case the collision
strategy is known as the open addressing technique. Primary clusteringis also worse when the hash table (available storage) is relatively full.
Variations in the linear method which avoid primary clustering
involve making the step size a variable. One way is to set s equal toai + bi2 on the /th step. Another is to invoke a random number
generator which calculates the step size afresh each time. These last twocollision handling methods are called the quadratic and random method
respectively. Although they avoid primary clustering they arenevertheless subject to secondary clustering, which is caused by keys
hashing to the same address and following the same sequence in searchof an empty location. Even this can be avoided, see for example Belland Kaman17.
The second class of collision handling methods involves extra storage
space which is used to chain together collided records. When a collisionoccurs at a hash address it may be because it is the head of a chain ofrecords which have all hashed to that address, or it may be that a record
is stored there which belongs to a chain starting at some other address.
In both cases a free location is needed which in the first case is simply
linked in and stores the new record, in the second case the intermediatechain element is moved to the free location and the new record isstored at its own hash address thus starting a new chain (a one-element
chain so far). A variation on this method is to use a two-level store. At
the first level we have a hash table, at the second level we have a bumptable which contains all the collided records. At a hash address in thehash table we will find either, a record if no collisions have taken placeat that address, or, a pointer to a chain of records which collided at that
address. This latter chaining method has the advantage that records
need never be moved once they have been entered in the bump table.
The storage overhead is larger since records are put in the bump table
before the hash table is full.
For both classes of collision strategies one needs to be careful about
deletions. For the linear, quadratic etc. collision handling strategies wemust ensure that when we delete a record at an address we do not makerecords which collided at that address unreachable. Similarly with thechaining method we must ensure that a deleted record does not leave a
gap in the chain, that is, after deletion the chain must be reconnected.
The advantages of hashing are several. Firstly it is simple. Secondly
its insertion and search strategies are identical. Insertion is merely afailed search. If Kt is the hashed key, then if a search of the collision
sequence fails to turn up a match in Kt, its record is simply inserted at76

FILE STRUCTURES

the end of the sequence at the next free location. Thirdly, the searchtime is independent of the number of keys to be inserted.
The application of hashing in IR has tended to be in the area of table
construction and look-up procedures. An obvious application is whenconstructing the set of conflation classes during text processing. In
Chapter 2, I gave an exmaple of a document representative as simply alist of class names, each name standing for a set of equivalent words.
During a retrieval operation, a query will first be converted into a list ofclass names. To do this each significant word needs to be looked up in adictionary which gives the name of the class to which it belongs. Clearly
there is a case for hashing. We simply apply the hashing function to theword and find the name of the conflation class to which it belongs at
the hash address. A similar example is given in great detail by Murray18.
Finally, let me recommend two very readable discussions on hashing,
one is in Page and Wilson19, the other is in Knuth’s third volume14.

Bibliographic remarks

There is now a vast literature on file structures although there are very
few survey articles. Where possible I shall point to some of the moredetailed discussions which emphasise an application in IR. Of course
the chapter on file organisation in the Annual Review is a good sourceof references as well.
A general article on data structures of a more philosophical nature
well worth reading is Mealey20. It tries to clarify some of our notions
about data thereby constructing a theory of data.
A description of the use of a sequential file in an on-line
environment may be found in Negus and Hall21. The effectiveness andefficiency of an inverted file has been extensively compared with a filestructure based on clustering by Murray22. Ein-Dor23 has done acomprehensive comparison between an inverted file and a tree
structured file. It is hard to find a discussion of an index-sequential filewhich makes special reference to the needs of document retrieval.
Index-sequential organisation is now considered to be basic software
which can be used to implement a variety of other file organisations.
Nevertheless it is worth studying some of the aspects of its
implementation. For this I recommed the paper by McDonell andMontgomery24 who give a detailed description of an implementation
for a mini-computer. Multi-lists and cellular multi-lists are fairly wellcovered by Lefkovitz25. Ring structures have been very popular in CAD
and have been written up by Gray25. Extensive use was made of amodified threaded list by Van Rijsbergen27 in his cluster-based retrieval
experiments. The doubly chained tree has been adequately dealt with77

FILE STRUCTURES

by Stanfel7,8 and Patt9. The use of trees in IR goes back a long way
and the early papers by Salton28 and Sussenguth29 are well worth
reading. Also interesting is the early paper by Windley30 which gives
some theoretical results about the expected search time. The use ofhashing in document retrieval is dealt with in Higgins and Smith31 andChou32.
It has become fashionable to refer to document collections whichhave been clustered as clustered files. I have gone to some pains to
avoid the use of this terminology because of the conceptual difference
that exists between a structure which is inherent in the data and can be
discovered by clustering, and an organisation of the data to facilitate its
manipulation inside a computer. Unfortunately this distinction
becomes somewhat blurred when clustering techniques are used togenerate a physical organisation of data. For example, the work by Bellet al. 3 3 is of this nature. Furthermore, it has recently become popular
to cluster records simply to improve the efficiency of retrieval.
Buckhard and Keller34 base the design of a file structure on maximal
complete subgraphs (or cliques). Hatfield and Gerald35 have designed apaging algorithm for a virtual memory store based on clustering. Simonand Guiho36 look at methods for preserving ‘clusters’ in the data when
it is mapped onto a physical storage device.
Some of the work that has been largely ignored in this chapter, butwhich is nevertheless of impoftance when considering the implementa­tion of a file structure, is concerned directly with the physicalorganisation of a storage device in terms of block sizes, etc.
Unfortunately, general statements about this are rather hard to makebecause the organisation tends to depend on the hardware
characteristics of the device and computer. Representative of work inthis area is the paper by Lum et al.31.
Finally, one approach to data organisation which is in spirit like theone based on automatic classification, is that presented by Codd38 who
describes the natural structure of the data in terms of n-ary relations.

References
1. HSIAO, D. and HARARY, F., ‘A formal system for information retrieval
from files’, Communications o f the ACM, 13, 67-73 (1970)
2. ROBERTS, D. C., ‘File organization techniques’, Advances in Computers, 12,
115-174 (1972)
3. BERTZISS, A, T., Data Structures: Theory and Practice, Academic Press,
London and New York (1971)
4. DODD, G. G., ‘Elements of data management systems’, Computing Surveys,
1, 117-133 (1969)

78

FILE STRUCTURES
5. CLIMENSON, W. D., ‘File organization and search techniques’, Annual
Review o f Information Science and Technology, 1, 107-135 (1966)
6. FOSTER, J. M., List Processing, Macdonald, London; and American Elsevier
Inc., New York (1967)
7. STANFEL, L. E., ‘Practical aspect of doubly chained trees for retrieval’,
Journal o f the ACM, 19,425-436 (1972)
8. STANFEL, L. E., ‘Optimal trees for a class of information retrieval
problems’, Information Storage and Retrieval, 9, 43-59 (1973)
9. PATT, Y. N., ‘Minimum search tree structure for data partitioned into pages’,
IEEE Transations on Computers, C-21, 961-967 (1972)
10. BERGE, C., The Theory o f Graphs and its Applications, Methuen, London(1966)
11. HARARY, F„ NORMAN, R. Z. and CARTWRIGHT, D., Structural Models:
An Introduction to the Theory o f Directed Graphs, Wiley, New York (1966)
12. ORE, O., Graphs and their Uses, Random House, New York (1963)
13. KNUTH, D. E., The A rt o f Computer Programming, Vol. 1, Fundamental
Algorithms, Addison-Wesley, Reading, Massachusetts (1968)
14. KNUTH, D. E., The A rt o f Computer Programming, Vol. 3, Sorting and
Searching, Addison-Wesley, Reading, Massachusetts (1973)
15. MORRIS, R., ‘Scatter storage techniques’, Communications o f the ACM, 11,35-38 (1968)
16. LUM, V. Y., YUEN, P. S. T. and DODD, M., ‘Key-to-address transform
techniques: a fundamental performance study on large existing formatted
files’, Communications o f the ACM, 14, 228-239 (1971)
17. BELL, J. R. and KAMAN, C. H., ‘The linear quotient hash code’,
Communications o f the ACM, 13, 675-677 (1970)
18. MURRAY, D. M., ‘A scatter storage scheme for dictionary lookups’. In:
Report ISR-16 to the National Science Foundation, Section II, Cornell
University, Department of Computer Science (1969)
19. PAGE, E. S. and WILSON, L. B., Information Representation andManipulation in a Computer, Cambridge University Press, Cambridge (1973)
20. MEALEY, G. H., ‘Another look at data’, Proceedings AFIP Fall Joint
Computer Conference, 525-534 (1967)
21. NEGUS, A. E. and HALL, J. L., ‘Towards an effective on-line reference
retrieval system’, Library Memo CLM-LM2/71, U.K. Atomic Energy
Authority, Research Group (1971)
22. MURRAY, D. M., ‘Document retrieval based on clustered files’, Ph.D. Thesis,
Cornell University Report ISR-20 to National Science Foundation and to the
National Library of Medicine (1972)
23. EIN-DOR, P., ‘The comparative efficiency o f two dictionary structures for
document retrieval, Infor Journal, 12, 87-108 (1974)
24. McDONELL, K.J. and MONTGOMERY, A. Y., ‘The design of indexedsequential files’, The Australian Computer Journal, 5, 115-126 (1973)
25. LEFKOVITZ, D., File Structures for On-line Systems, Spartan Books, NewYork (1969)
26. GRAY, J. C., ‘Compound data structure for computer aided design: asu r v e y Proceedings ACM National Meeting, 355-365 (1967)
27. VAN RIJSBERGEN, C. J., ‘An algorithm for information structuring andretrieval’, Computer Journal, 1 4 ,407-412 (1971)
28. SALTON,
G., Manipulation of trees in information retrieval’,Communications o f the ACM, 5, 103-114 (1962)
29. SUSSENGUTH, E. H., ‘Use of tree structures for processing files’,Communications o f the ACM, 6, 272-279 (1963)

79

FILE STRUCTURES
30. WINDLEY, P. F., ‘Trees, forests and rearranging’, Computer Journal, 3,84-88 (1960)
31. HIGGINS, L. D. and SMITH, F. J., ‘Disc access algorithms’, Computer
Journal, 14, 249-253 (1971)
32. CHOU, C. K., ‘Algorithms for hash coding and document classification’,Ph.D. Thesis, University of Illinois (1972)
33. BELL, C. J., ALDRED, B. K. and ROGERS, T. W„ ‘Adaptability to change
in large data base information retrieval systems’, Report No. UKSC-0027, UK
Scientific Centre, IBM United Kingdom Limited, Neville Road, Peterlee,County Durham, U.K. (1972)
34. BURKHARD, W. A. and KELLER, R. M., ‘Some approaches to best-match
file searching’, Communications o f the ACM, 16, 230-236 (1973)
35. HATFIELD, D. J. and GERALD, J., ‘Program restructuring for virtual
memory \ IBM Systems Journal, 10, 168-192 (1971)
36. SIMON, J. C. and GUIHO, G., ‘On algorithms preserving neighbourhood tofile and retrieve information in a memory’, International Journal Computer
Information Sciences, 1, 3-15 (CR 23923) (1972)
37. LUM, V. Y., LING, H. and SENKO, M. E., ‘Analysis of a complex data
management access method by simulation modelling’, Proceedings AFIP Fall
Joint Computer Conference, 211-222 (1970)
38. CODD, E. F., ‘A relational model of data for large shared data banks’,Communications o f the ACM, 13, 377-387 (1970)80