Design of the TechInfo Search Engine

		(adapted from the DESIGN document of 
		the WAIS system, written by Brewster
		Kahle, brewster@think.com)

The serial indexer is a simple inverted file system adapted from the
WAIS inverted file system.

DATABASE FILES

The original WAIS serial indexer parsed files and created an inverted
file index made up of 7 files.  Most of these files existed for the
benefit of file I/O.  Since TechInfo takes care of most of the file
I/O, a lot of these files were eliminated in the adaptation of the
source for use with TechInfo.

What remained when the pruning was done were two files: an inverted
index file, and a dictionary file. For examle, for a database named
"index" the files would be:

 *  index.inv -- the "postings file" that is a term followed by a list of
entries each of which describe where that word occurs in the original files.
A posting is a weight, doc_number, and character_position.  In the
original code, the doc_number was a reference into another file, the
document file. In the modified code, the doc_number is the node id of
the file. Thus, when searches are run on the index, the node id of
each match is returned to TechInfo.

This file is indexed with the dictionary (dct) file.  The terms are in
alphabetical order.

 *  index.dct -- dictionary file which is a 2 level b-tree.  The first block
is pointers to the every 1000th entry in the rest of the dictionary file.
Each entry is a fixed-length record of the word with the position into the
rest of the file.  The rest of the file are blocks just like the first
block, but each entry is the word plus the position of it in the inverted
file (inv).  The whole dictionary is in alphabetical order.

INDEXING

A new index is built by parsing the input files and finding the words in it.
The words are then passed to routines defined in irext.h which define the
frontend/backend boundary.  

The serial indexer creates intermediate inv files starting at inv0 then
inv1 etc.  These are created by accumulating the words in a memory
hashtable.  Each invN file is in alphabetical order, so they can be merged
easily into one inv file.  This merging has been modified, so that it
takes place as the files are created. This slows down the indexing
process, but saves space.

On the final merge, a dictionary file is produced by dumping the positions
of the start of terms in the final inverted file.


SEARCHING

A search request is received from the TechInfo client as a "J"
command, followed by a string of words to be searched, an optional
node id, and an optional maximum number of documents.  The string is
parsed for its seed words, and the words are passed to a function
search_word (defined in irext.h).  The word is looked up, and a list
of node id's is compiled. This list is passed back to the techinfo
server, which looks up and displays up the documents on the list.
If the optional node id is given, only documents beneath that node in
the web are displayed.

The serial backend does this by loading the postings for a particular term
and then adding it into a score hash table.  The score array has an entry for
each document.  A document gets its score increased by containing terms in
the query.

NOTES

The code can be updated when newer versions of the WAIS search engine
are released, simply by incorporating useful changes into the current
TechInfo source. Bear in mind that anything relating to the z39-50
protocol or file I/O should be eliminated, since these functions are
taken care of by the TechInfo server and front end.