Document retrieval using a serial bit string search

Nearest neighbour searching in serial files using text signatures

A nearest neighbour search procedure is described for use with serial files of textual data. The procedure involves the grouping of records into blocks, each of which is characterised by a fixed-length bit string. A comparable query bit string may then be matched against each of these bit strings, and an upper bound calculation used to identify those blocks which need to be inspected in detail if the document that is most similar to the query is to be identified. Experiments with three small collections of documents and queries are used to test the efficiency of the approach. The experiments show that reduc tions in computation are possible, although the precise savings are crucially dependent upon a range of factors including the frequency characteristics of the documents and queries, the similarity coefficients, and the sizes of the bit strings and of the blocks.

Information retrieval research in the Department of Information Studies, University of Sheffield: 1965-1985

This paper discusses research which was carried out at the Department of Information Studies, University of Sheffield in the period 1965 to 1985 into storage and retrieval techniques for databases of textual and chemical structure data. The research includes the development of methods for the auto matic production of printed subject indexes and for the inde xing and retrieval of chemical structures and chemical reac tions, the variety generation method for the analysis, characterization and storage of data in a range of types of textual database, the prediction of biological activity in chemical compounds, and the design of document retrieval systems.

Efficiency of text scanning in bibliographic databases using microprocessor-based, multiprocessor networks

This paper reports an evaluation of the efficiency of text scanning achievable from a microprocessor-based, multi processing system which uses Inmos transputers. The Boyer-Moore pattern matching algorithm was used to search 35 natural language quenes against a file of 1000 titles and abstracts taken from the Library and Information Science Ab stracts database. A model of searching using a singly-linked chain containing up to 11 transputers was carried out: the maximum speed-up obtained with this size of network was 10.4 with a processor utilization of 0.95, both figures being close to the ideal of 11.0 and 1.0. Expenments with a nearest neighbour searching algorithm for serial document files demonstrate the need to keep the processors fully occupied with computational work if a high degree of speed-up is to be obtained.

Implementing ranking strategies using text signatures

Signature files provide an efficient access method for text in documents, but retrieval is usually limited to finding documents that contain a specified Boolean pattern of words. Effective retrieval requires that documents with similar meanings be found through a process of plausible inference. The simplest way of implementing this retrieval process is to rank documents in order of their probability of relevance. In this paper techniques are described for implementing probabilistic ranking strategies with sequential and bit-sliced signature tiles and the limitations of these implementations with regard to their effectiveness are pointed out. A detailed comparison is made between signature-based ranking techniques and ranking using term-based document representatives and inverted files. The comparison shows that term-based representations are at least competitive (in terms of efficiency) with signature files and, in some situations, superior.