Software and hardware techniques for string searching in serial document databases

This paper considers the use of text signatures and of parallel computer hardware to increase the efficiency of text scanning in serial document files. After a review of software and hardware techniques for text scanning, the characteristics of text signature systems for document retrieval are discussed, in particular the relationship between text signature length and both the efficiency and the effectiveness of searching. A parallel pattern matching algorithm is then described for use with the ICL Distributed Array Processor, a highly parallel SIMD array processor. The efficiency of this algorithm is compared with that of the Aho-Corasick pattern matching algorithm when implemented on a conventional minicomputer. Microprocessor-based multiprocessing networks are becoming widely available as a means of implementing MIMD parallelism. Experiments with the Boyer-Moore pattern matching algorithm on a network of INMOS transputers demonstrate near-linear speed-ups for networks containing up to 11 transputers.