The Utah Retrieval System Architecture provides an excellent testbed for the development and testing of new algorithms or techniques for information retrieval. URSA™ is a message-based structure capable of running on a variety of system configurations, ranging from a single mainframe processor to a system distributed across a number of dissimilar processors. It can readily support a variety of specialized backend processors, such as high-speed search engines.

As databases become very large, conventional digital computers cannot provide satisfactory response time. This is particularly true for text databases, which must often be several orders of magnitude larger than formatted databases to store a useful amount of information. Even the standard techniques for improving system performance (such as inverted files) may not be sufficient to give the desired performance, and the use of an unconventional hardware organization may become necessary.A variety of different organizations has been proposed to enhance processing of text retrieval operations. Most of these have concentrated on the design of fast, efficient search engines. These can be divided into three classes: associative memories, cellular pattern matchers, and finite state automata. The advantages and disadvantages inherent in each of these approaches are discussed, along with a number of proposed implementations. Finally, the text retrieval system under development at the University of Utah is discussed in more detail.

The design and operation of a new class of hardware-based pattern matchers, such as would be used in a backended database processor in a full-text or other retrieval system, is presented. This recognizer is based on a unique implementation technique for finite state automata consisting of partitioning the state table among a number of simple digital machines. It avoids the problems generally associated with implementing finite state machines, such as large state table memories, complex control mechanisms, and state encodings. Because it consists primarily of memory, with its high regularity and density, needs only limited static interconnections, and operates at a relatively low speed, it can be easily constructed using integrated circuit techniques. After a brief discussion of other pattern-matching hardware, the structure and operation of the partitioned finite state automaton is given, along with a simplified discussion of how the state tables are partitioned. The expected performance of the resulting system and the state table partitioning programs is then discussed.

The "one-hot" row assignment for asynchronous circuits, in which every row in a flow table has exactly one of the feedback variables that equals the value 1, provides a straightforward method for circuit synthesis. Once a flow table has been constructed, the state equations can be directly written, without requiring any procedure to ensure a race-free assignment. Furthermore, it can implement any arbitrary fundamental mode asynchronous circuit, not depending on a specific signaling protocol for its correct operation. An alternate view of one-hot asynchronous circuits is given, with a simple set-reset flip-flop for each state. Although this may seem excessive compared to implementations with encoded state variables, for many circuits their one-hot implementation is comparable in cost to other asynchronous implementations.

In inverted file database systems (and in a number of other applications), much of the processing consists of merging two or more previously sorted lists based on a Boolean expression. Conventional general purpose computers are not well suited for this type of operation, with even well written programs utilizing less than 10 percent of the available memory capacity for actual processing of data. However, a low-cost special purpose backend processor can be used to efficiently handle the list merging operations, freeing the conventional processor for other uses.

Many people have suggested adding scanning logic to a rotating memory system, such as disk or shift registers, to allow faster execution of database operations. Most of these have been concerned with producing a form of associative memory which is then used to implement one or more of the models for information storage and retrieval, such as relational or hierarchical. While these are capable of searching for simple character strings, they are incapable of handling the complex patterns sometimes necessary for textual information retrieval. In addition, textual information retrieval does not lend itself to highly formatted databases, encoding of information, or arbitrary ordering of data, concepts common to the other structures.

In inverted file database systems, index lists consisting of pointers to items within the database are combined to form a list of items which potentially satisfy a user's query. This list merging is similar to the common data processing operation of combining two or more sorted input files to form a sorted output file, and generally represents a large percentage of the computer time used by the retrieval system. Unfortunately, a general purpose digital computer is better suited for complicated numeric processing rather than the simple combining of data. The overhead of adjusting and checking pointers, aligning data, and testing for completion of the operation overwhelm the processing of the data. A specialized processor can perform most of these overhead operations in parallel with the processing of the data, thereby offering speed increases by a factor from 10 to 100 over conventional computers, depending on whether a higher speed memory is used for storing the lists. These processors can also be combined into networks capable of directly forming the result of a complex expression, with another order of magnitude speed increase possible. The programming and operation of these processors and networks is discussed, and comparisons are made with the speed and efficiency of conventional general purpose computers.