Bibliographic pattern matching using the ICL Distributed Array Processor

This article discusses the use of the ICL Distributed Array Processor (DAP), a highly parallel array processor containing 4096 processing elements, for pattern‐matching operations in a bibliographic retrieval system. The hardware and software features of the DAP are described, together with a pattern‐matching algorithm that makes full use of the DAP's parallelism. This algorithm can be used to search for exact patterns, right‐hand or left‐hand truncated patterns, embedded patterns, patterns containing fixed‐length (FLDC) or variable‐length (VLDC) don't care characters, and patterns that specify adjacent words. Experiments with a set of 898 query patterns and 2472 titles and abstracts from the INSPEC database show that right‐hand truncation searches can be carried out on the DAP about ten times faster than searches using the Aho‐Corasick pattern‐matching algorithm on a Prime 550 minicomputer, the relative advantage of the DAP increasing linearly with a decrease in the number of query patterns. Simulated FLDC and VLDC searches on the DAP take about two and three times as long as right‐hand truncation searches, respectively. © 1988 John Wiley & Sons, Inc.