Abstract This paper describes three spelling checkers implemented at the University of Western Ontario. The first is interesting for its functionality and high compression of its dictionary; the second for its unexpected failure and the third for using the lesson of the previous to good advantage. The principal contributions of this work are a compressed dictionary structure at 12 bits per dictionary token; and the ability to offer suggested corrections from a structure without the words explicitly stored.

A Bloom-filter-based semijoin algorithm for distributed database systems is presented. This algorithm reduces communications costs to process a distributed natural join as much as possible with a filter approach. An optimal filter is developed in pieces. Filter information is used both to recognize when the semijoin will cease to be effective and to optimally process the semijoin. An ineffective semijoin will be quickly and cheaply recognized. An effective semijoin will use all of the transmitted bits optimally.>

A highly compressed index for a collection of variable-sized documents is described. Arrays of small Bloom filters are used to efficiently locate documents where the search probe contains ‘anded’ and ‘ored’ combinations of words. Theoretical and experimental results are reported. The method is applicable to unplanned searching of large text files. We further describe a method to provide an index to the filters. Thus only a small proportion of the compressed filter need be examined. The method is highly amenable to parallel processing.

We describe and analyse a dynamic hashing method called ‘Spiral Storage’. Dynamic hashing methods extend the power of conventional hashing methods by avoiding the need to have good initial estimates of the storage demand. The file storage space will grow or shrink with demand. ‘Spiral Storage’ is the only known dynamic hashing method which provides constant average performance while the storage space changes in proportion to the storage demand. The performance of the method with link chained overflow is investigated. Results of analysis and of simulations confirm the utility of the method.

B-tree structures with the restriction that all data records are stored at the leaves of the tree are investigated from the standpoint of recovery from hardware and software errors. A technique is presented for maintaining the original file inviolate—which could reside on read only memory—and recording changes in a separate area. Standard algorithms are used for direct access search and hence retrieval time is not affected. Update algorithms are slightly altered to direct all modifications to a separate area. Expressions are developed for storage and time penalties. Due to system overheads, the range of application is limited to files which can tolerate small blocking factors. The technique is contrasted to differential files and a direct point comparison is made to an earlier paper by Severance and Lohman.

A new method is described and tested for using an unreliable character recognition device to produce a reliable index for a collection of documents. All highly likely substitution errors of the recognition device are handled by transforming characters which confuse readily into the same pseudocharacter. An analysis of the method is done showing the expected precision (fraction of words correctly found to words present) and recall (fraction of words retrieved properly to those which were retrieved). Published substitution error matrices were employed, along with a large file of words and word frequencies to evaluate the method. Performance was surprisingly good. Suggestions for further enhancements are given.

This work involves techniques to determine optimal blocking arrangements for sequentially processed magnetic files. It is an extension to the work by Waters (1971), who presents a method of optimally blocking files in a single job. We consider a group of jobs, run with different frequencies, where constraints exist between jobs due to common files. Practical constraints on the maximum size of a physical record are also included. Two operating environments are considered. In the first the amount of storage available for a job is known. In the second environment, the amount of storage available for a job is not predetermined and is found by the minimisation of a cost function. A quadratic programming technique presented by Ravindran (1972) is employed in the solution.