The timing of hunt is complex. Normally the hash table is overfull, so that there will be many false drops on any single term; but a multi-term query will have few false drops on all terms. Thus if a query is underspecified (one search term) many potential items will be examined and discarded as false drops, wasting time. If the query is overspecified (a dozen search terms) many keys will be examined only to verify that the single item under consideration has that key posted. The variation of search time with number of keys is shown in the table below. Queries of varying length were constructed to retrieve a particular document from the file of references. In the sequence to the left, search terms were chosen so as to select the desired paper as quickly as possible. In the sequence on the right, terms were chosen inefficiently, so that the query did not uniquely select the desired document until four keys had been used. The same document was the target in each case, and the final set of eight keys are also identical; the differences at five, six and seven keys are produced by measurement error, not by the slightly different key lists.

The careful reader will have noted an enormous discrepancy between these times and the earlier quoted time of around 1.9 seconds for a search. The times here are purely for the search and retrieval: they are measured by running many searches through a single invocation of the hunt program alone. The normal retrieval operation involves using the shell to set up a pipeline through mkey to hunt and starting both processes; this adds a fixed overhead of about 1.7 seconds of processor time to any single search. Furthermore, remember that all these times are processor times: on a typical morning on our \s-2PDP\s0 11/70 system, with about one dozen people logged on, to obtain 1 second of processor time for the search program took between 2 and 12 seconds of real time, with a median of 3.9 seconds and a mean of 4.8 seconds. Thus, although the work involved in a single search may be only 200 milliseconds, after you add the 1.7 seconds of startup processor time and then assume a 4:1 elapsed/processor time ratio, it will be 8 seconds before any response is printed.

The major application of the retrieval software is refer, which is a troff preprocessor like eqn . .[ kernighan cherry acm 1975 .] It scans its input looking for items of the form \*.[ imprecise citation \*.\^] where an imprecise citation is merely a string of words found in the relevant bibliographic citation. This is translated into a properly formatted reference. If the imprecise citation does not correctly identify a single paper (either selecting no papers or too many) a message is given. The data base of citations searched may be tailored to each system, and individual users may specify their own citation files. On our system, the default data base is accumulated from the publication lists of the members of our organization, plus about half a dozen personal bibliographies that were collected. The present total is about 4300 citations, but this increases steadily. Even now, the data base covers a large fraction of local citations.

For example, the reference for the eqn paper above was specified as \*.\*.\*. preprocessor like .I eqn. .[ kernighan cherry acm 1975 .] It scans its input looking for items \*.\*.\*. This paper was itself printed using refer. The above input text was processed by refer as well as tbl and troff by the command refer memo-file | tbl | troff -ms and the reference was automatically translated into a correct citation to the ACM paper on mathematical typesetting.

The procedure to use to place a reference in a paper using refer is as follows. First, use the lookbib command to check that the paper is in the data base and to find out what keys are necessary to retrieve it. This is done by typing lookbib and then typing some potential queries until a suitable query is found. For example, had one started to find the eqn paper shown above by presenting the query $ lookbib kernighan cherry (EOT) lookbib would have found several items; experimentation would quickly have shown that the query given above is adequate. Overspecifying the query is of course harmless. A particularly careful reader may have noticed that ``acm'' does not appear in the printed citation; we have supplemented some of the data base items with common extra keywords, such as common abbreviations for journals or other sources, to aid in searching.

If the reference is in the data base, the query that retrieved it can be inserted in the text, between \*.[ and \*.\^] brackets. If it is not in the data base, it can be typed into a private file of references, using the format discussed in the next section, and then the -p option used to search this private file. Such a command might read (if the private references are called myfile ) refer -p myfile document | tbl | eqn | troff -ms \*. \*. \*. where tbl and/or eqn could be omitted if not needed. The use of the -ms macros .[ lesk typing documents unix gcos .] or some other macro package, however, is essential. Refer only generates the data for the references; exact formatting is done by some macro package, and if none is supplied the references will not be printed.

By default, the references are numbered sequentially, and the -ms macros format references as footnotes at the bottom of the page. This memorandum is an example of that style. Other possibilities are discussed in section 5 below.

A reference file is a set of bibliographic references usable with refer. It can be indexed using the software described in section 2 for fast searching. What refer does is to read the input document stream, looking for imprecise citation references. It then searches through reference files to find the full citations, and inserts them into the document. The format of the full citation is arranged to make it convenient for a macro package, such as the -ms macros, to format the reference for printing. Since the format of the final reference is determined by the desired style of output, which is determined by the macros used, refer avoids forcing any kind of reference appearance. All it does is define a set of string registers which contain the basic information about the reference; and provide a macro call which is expanded by the macro package to format the reference. It is the responsibility of the final macro package to see that the reference is actually printed; if no macros are used, and the output of refer fed untranslated to troff, nothing at all will be printed.

The strings defined by refer are taken directly from the files of references, which are in the following format. The references should be separated by blank lines. Each reference is a sequence of lines beginning with % and followed by a key-letter. The remainder of that line, and successive lines until the next line beginning with % , contain the information specified by the key-letter. In general, refer does not interpret the information, but merely presents it to the macro package for final formatting. A user with a separate macro package, for example, can add new key-letters or use the existing ones for other purposes without bothering refer.

The meaning of the key-letters given below, in particular, is that assigned by the -ms macros. Not all information, obviously, is used with each citation. For example, if a document is both an internal memorandum and a journal article, the macros ignore the memorandum version and cite only the journal article. Some kinds of information are not used at all in printing the reference; if a user does not like finding references by specifying title or author keywords, and prefers to add specific keywords to the citation, a field is available which is searched but not printed (\f3K\f1).

The key letters currently recognized by refer and -ms, with the kind of information implied, are: .KS

In some cases users wish to suspend the searching, and merely use the reference macro formatting. That is, the user doesn't want to provide a search key between \*.[ and \*.\^] brackets, but merely the reference lines for the appropriate document. Alternatively, the user can wish to add a few fields to those in the reference as in the standard file, or override some fields. Altering or replacing fields, or supplying whole references, is easily done by inserting lines beginning with % ; any such line is taken as direct input to the reference processor rather than keys to be searched. Thus \*.[ key1 key2 key3 \*.\*.\*. %Q New format item %R Override report name \*.\^] makes the indicated changes to the result of searching for the keys. All of the search keys must be given before the first \f3%\f1 line.

If no search keys are provided, an entire citation can be provided in-line in the text. For example, if the eqn paper citation were to be inserted in this way, rather than by searching for it in the data base, the input would read \*.\*.\*. preprocessor like .I eqn. .[ %A B. W. Kernighan %A L. L. Cherry %T A System for Typesetting Mathematics %J Comm. ACM %V 18 %N 3 %P 151-157 %D March 1975 .] It scans its input looking for items \*.\*.\*. This would produce a citation of the same appearance as that resulting from the file search.

As shown, fields are normally turned into troff strings. Sometimes users would rather have them defined as macros, so that other troff commands can be placed into the data. When this is necessary, simply double the control character % in the data. Thus the input .[ %V 23 %%M Bell Laboratories, Murray Hill, N.J. 07974 .] is processed by refer into .ds [V 23 .de [M Bell Laboratories, Murray Hill, N.J. 07974 .. The information after %%M is defined as a macro to be invoked by .[M while the information after %V is turned into a string to be invoked by \e\(**([V . At present -ms expects all information as strings.

Normally, the combination of refer and -ms formats output as troff footnotes which are consecutively numbered and placed at the bottom of the page. However, options exist to place the references at the end; to arrange references alphabetically by senior author; and to indicate references by strings in the text of the form [Name1975a] rather than by number. Whenever references are not placed at the bottom of a page identical references are coalesced.

For example, the -e option to refer specifies that references are to be collected; in this case they are output whenever the sequence \*.[ $LIST$ \*.\^] is encountered. Thus, to place references at the end of a paper, the user would run refer with the -e option and place the above $LIST$ commands after the last line of the text. Refer will then move all the references to that point. To aid in formatting the collected references, refer writes the references preceded by the line .]< and followed by the line .]> to invoke special macros before and after the references.

Another possible option to refer is the -s option to specify sorting of references. The default, of course, is to list references in the order presented. The -s option implies the -e option, and thus requires a \*.[ $LIST$ \*.\^] entry to call out the reference list. The -s option may be followed by a string of letters, numbers, and `+' signs indicating how the references are to be sorted. The sort is done using the fields whose key-letters are in the string as sorting keys; the numbers indicate how many of the fields are to be considered, with `+' taken as a large number. Thus the default is -sAD meaning ``Sort on senior author, then date.'' To sort on all authors and then title, specify -sA+T . And to sort on two authors and then the journal, write -sA2J .

Other options to refer change the signal or label inserted in the text for each reference. Normally these are just sequential numbers, and their exact placement (within brackets, as superscripts, etc.) is determined by the macro package. The -l option replaces reference numbers by strings composed of the senior author's last name, the date, and a disambiguating letter. If a number follows the l as in -l3 only that many letters of the last name are used in the label string. To abbreviate the date as well the form \f3-l\f2m,n\f1 shortens the last name to the first m letters and the date to the last n digits. For example, the option -l3,2 would refer to the eqn paper (reference 3) by the signal Ker75a , since it is the first cited reference by Kernighan in 1975.

A user wishing to specify particular labels for a private bibliography may use the -k option. Specifying \f3-k\f2x\f1 causes the field \f2x\f1 to be used as a label. The default is \f3L\f1. If this field ends in \f3-\f1, that character is replaced by a sequence letter; otherwise the field is used exactly as given.

If none of the refer -produced signals are desired, the -b option entirely suppresses automatic text signals.

If the user wishes to override the -ms treatment of the reference signal (which is normally to enclose the number in brackets in nroff and make it a superscript in troff\\| ) this can be done easily. If the lines .[ or .] contain anything following these characters, the remainders of these lines are used to surround the reference signal, instead of the default. Thus, for example, to say ``See reference (2).'' and avoid ``See reference.\s-3\u2\d\s+3'' the input might appear See reference \*.[ ( imprecise citation ... \*.\^])\*. Note that blanks are significant in this construction. If a permanent change is desired in the style of reference signals, however, it is probably easier to redefine the strings [. and .] (which are used to bracket each signal) than to change each citation.

Although normally refer limits itself to retrieving the data for the reference, and leaves to a macro package the job of arranging that data as required by the local format, there are two special options for rearrangements that can not be done by macro packages. The -c option puts fields into all upper case (C\s-2APS\s+2-S\s-2MALL\s+2 C\s-2APS\s+2 in troff output). The key-letters indicated what information is to be translated to upper case follow the c , so that -cAJ means that authors' names and journals are to be in caps. The -a option writes the names of authors last name first, that is "A. D. Hall, Jr." is written as "Hall, A. D. Jr" . The citation form of the "Journal of the ACM" , for example, would require both -cA and -a options. This produces authors' names in the style K\s-2ERNIGHAN\s0, B. W. \s-2AND\s0 C\s-2HERRY\s0, L. L.\& .R for the previous example. The -a option may be followed by a number to indicate how many author names should be reversed; -a1 (without any -c option) would produce Kernighan, B. W. and L. L. Cherry, .R for example.

Finally, there is also the previously-mentioned -p option to let the user specify a private file of references to be searched before the public files. Note that refer does not insist on a previously made index for these files. If a file is named which contains reference data but is not indexed, it will be searched (more slowly) by refer using fgrep. In this way it is easy for users to keep small files of new references, which can later be added to the public data bases. .SG MH-1274-MEL-\s8UNIX\s0