Hardware for searching very large text databases

ABSTRACT

This paper discusses the problem of searching very large text databases. It is shown that conventional techniques for searching current databases cannot be scaled up to larger ones, and that it is necessary to build hardware to search the database in parallel if reasonable search times are expected. The part of the search process requiring the highest bandwidth is scanning the database to detect instances of search terms. Methods of doing this in hardware that have been mentioned in the literature are examined, and design criteria for term matchers are discussed. A new design that uses a nondeterministic finite state automaton to control matching, is introduced, its operation is explained, and the practicality of using it in a real system is discussed.

REFERENCES

• 1: McCarn, D. B., 'Online Services of the National Library of Medicine,' Digest of Papers, COMPCON Fall 1978, Washington, D. C., pp. 48-53
• 2: Black, D. V., 'System Development Corporation's Search Service,' Digest of Papers, COMPCON Fall 1978, Washington, D. C., pp. 59-64.
• 3: Bayer, M. P., 'Dialog—An Online Retrieval System for Bibliographic Information,' Digest of Papers, COMPCON Fall 1978, Washington, D. C., pp. 54-58.
• 4: Sprowl, J. A., 'Computer-Assisted Legal Research—An Analysis of Full Text Document Retrieval Systems, Particularly the LEXIS System,' American Bar Foundation Research Journal, Jan. 1976, Vol. 1, No. 1, pp. 175-226.
• 5: Hollaar, L. A., 'Text Retrieval Computers,' Computer, March 1979, Vol. 12, No. 3 (ISSN 0018-9162), pp. 40-50.
• 6: 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]
• 7: Ozkarahan, E. A., Schuster, S. A., and Smith, K. C., 'RAP: an Associative processor for Data Base Management,' Proc. 1975 AFIPS Nat. Comp. Conf., Vol. 44, AFIPS Press, Montvale, N. J., pp. 379-387.
• 8: Su, S., and Lipovski, G. J., 'CASSM: A Cellular System for Very Large Databases,' Proc. Conf. on Very Large Data Bases, Sept. 1975, pp. 456-472.
• 9: David K. Hsiao , Krishnamurthi Kannan , Douglas S. Kerr, Structure memory designs for a database computer, Proceedings of the 1977 annual conference, p.343-350, January 1977 [doi>10.1145/800179.810225]
• 10: William Howard Stellhorn, A specialized computer for information retrieval., 1974
• 11: Hollaar, L. A., 'An Architecture for the Efficient Combining of Linearly Ordered Lists,' Second Workshop on Comp. Arch. for Non-Numeric Processing, Jan. 1976.
• 12: Hurley, B. J., 'Analysis of Computer Architectures for Information Retrieval,' M. S. Thesis, University of Illinois, Urbana, May 1976.
• 13: James Michael Milner, An analysis of rotational storage access scheduling in a multiprogrammed information retrieval system., 1976
• 14: R. M. Bird , J. B. Newsbaum , J. L. Trefftzs, Text file inversion: An evaluation, Proceedings of the fourth workshop on Computer architecture for non-numeric processing, p.42-50, August 01-04, 1978, Blue Mountain Lake, New York, United States [doi>10.1145/800128.804166]
• 15: Cheng, W. K., 'Multiprocessor for String Manipulation,' M. S. Thesis, University of Illinois, Urbana, Oct. 1977, pp. 22-65.
• 16: Stellhorn, W. H., 'A Processor for Direct Scanning of Text,' presented at First Nonnumeric Workshop, Dallas, Oct. 1974.
• 17: 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
• 18: Foster, M. J., and Kung, H. T., 'Design of Special Purpose VLSI Chips,' Computer, Jan. 1980, Vol. 13, No. 1, (ISSN 0018-9162), pp. 26-40.
• 19: Mules, D. W., and Warter, P. J., 'A String Matcher for an Approximate Matches,' Department of Electrical Engineering, University of Delaware, Newark, April, 1979.
• 20: George P. Copeland, String storage and searching for data base applications: Implementation on the INDY backend kernel, Proceedings of the fourth workshop on Computer architecture for non-numeric processing, p.8-17, August 01-04, 1978, Blue Mountain Lake, New York, United States [doi>10.1145/800128.804162]
• 21: Amar Mukhopadhyay, Hardware algorithms for nonnumeric computation, Proceedings of the 5th annual symposium on Computer architecture, p.8-16, April 03-05, 1978 [doi>10.1145/800094.803021]
• 22: Moore, G., et. al., 'High-Speed-Text-Search Design Contract Interim Report,' Operating Systems Incorporated, Woodland Hills, Calif., Jan. 1977, pp. 2-69-2-101.
• 23: 'High-Speed-Text-Search Design Contract Final Report', Operating Systems Incorporated, OSI:R77-009, April 1977, pp. 3-1-3-24.
• 24: Booth, T. L., Sequential Machine and Automata Theory, John Wiley and Sons, Inc., New York, 1968.
• 25: Stephen H. Unger, Asynchronous Sequential Switching Circuit, Krieger Publishing Co., Inc., Melbourne, FL, 1983

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Textual databases

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Management