Rotating memory processors for the matching of complex textual patterns

ABSTRACT

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. A description of the operations desirable in textual information retrieval is given, and contrasted to those operations allowed in non-textual systems. The general structure for a scanning processor is presented, and a number of different trade-offs in its design and operation are discussed.

REFERENCES

• 1: Hollaar, L A, and P A Emrath. An Improved Query Language for the EUREKA Textual Information Retrieval System. EUREKA Project Memorandum, Department of Computer Science, University of Illinois, in preparation.
• 2: L. A. Hollaar , B. J. Hurley , D. J. Kuck , D. H. Lawrie , J. W.S. Liu , J. M. Milner , J. K. Morgan , J. R. Rinewalt , W. H. Stellhorn, The design of system architectures for information retrieval, Proceedings of the annual conference, p.38-44, October 20-22, 1976, Houston, Texas, United States [doi>10.1145/800191.805522]
• 3: Hollaar, L A. Streaming Processor Networks for Combining Sorted Lists. Submitted to ACM Trans on Database Systems, September 1977.
• 4: Hollaar, L A, and W H Stellhorn. A Specialized Architecture for Textual Information Retrieval. Proc AFIPS NCC, June 1977.
• 5: Slotnick, D L. Logic per Track Devices. Advances in Computers 12, Academic Press, 1972.
• 6: Ozkarahan, E A, S A Schuster, and K C Smith. RAP—An Associative Processor for Data Base Management. Proc AFIPS NCC, 1975.
• 7: Healy, L D, K L Doty, and G J Lipovski. The Architecture of a Content Addressed Segment Sequential Storage. Proc AFIPS FJCC, 1972.
• 8: Chyuan Shiun Lin , Diane C. P. Smith , John Miles Smith, The design of a rotating associative memory for relational database applications, ACM Transactions on Database Systems (TODS), v.1 n.1, p.53-65, March 1976 [doi>10.1145/320434.320447]
• 9: David K. Hsiao , Krishnamurthi Kannan, The architecture of a database computer - a summary, Proceedings of the 3rd workshop on Computer architecture : Non-numeric processing, p.31-33, January 1977
• 10: Stellhorn W H. A Processor for Direct Scanning of Text. presented at First Non-Numeric Workshop, October 1974.
• 11: R. M. Bird , J. C. Tu , R. M. Worthy, Associative/parallel processors for searching very large textual data bases, Proceedings of the 3rd workshop on Computer architecture : Non-numeric processing, p.8-9, January 1977
• 12: D R Johnson. A Two Channel Movable Head Parallel Access Disk Memory System. EUREKA Project Memorandum, Department of Computer Science, University of Illinois, 1976.
• 13: Ralph E Griswold, The SNOBOL4 programming language, Bell Telephone Laboratories, 1968

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.0 General

General Terms:
Design, Management