Specialized merge processor networks for combining sorted lists

ABSTRACT

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.

REFERENCES

• 1: 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
• 2: Werner Buchholz, Planning a computer system: Project Stretch, McGraw-Hill, Inc., Hightstown, NJ, 1962
• 3: HOLLAAR, L.A. A list merging processor for inverted file information retrieval systems. Rep. 762, Dept. Comptr. Sci., U. of Illinois, Urbana-Champaign Ill., Oct. 1975.
• 4: 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]
• 5: HOLLAAR, L.A., AND STELLHORN, W.H. A specialized architecture for textual information retrieval. Proc AFIPS 1977 NCC, Vol. 46, AFIPS Press, Montvale, N.J., pp. 697-702.
• 6: Lee A. Hollaar, Rotating memory processors for the matching of complex textual patterns, Proceedings of the 5th annual symposium on Computer architecture, p.39-43, April 03-05, 1978 [doi>10.1145/800094.803025]
• 7: JOHNSON, D.R. A two channel movable head parallel access disk memory system. EUREKA proj. memo., Dept. Comptr. Sci., U. of Illinois, Urbana-Champaign, Ill., 1976.
• 8: MILNER, J.M. An analysis of rotational storage access scheduling in a multiprogrammed information retrieval system. Rep. 826, Dept. Comptr. Sci., U. of Illinois, Urbana-Champaign, Ill., Sept. 1976.
• 9: RINEWALT, J.R. Evaluation of selected features of the EUREKA full-text information retrieval system. Rep. 823, Dept. Comptr. Sci., U. of Illinois, Urbana-Champaign, Ill., Sept. 1976.
• 10: Gerard Salton, Dynamic information and library processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1975
• 11: STELLHORN, W.H. A specialized computer for information retrieval. Rep. 637, Dept. Comptr. Sci., U. of Illinois, Urbana-Champaign, Ill, Oct. 1974.
• 12: STELLHORN, W.H. An inverted file processor for information retrieval. IEEE Trans. Comptrs. C-26, 12 (Dec. 1977), 1258-1267.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

General Terms:
Design

Keywords:
backend processors, binary tree networks, computer system architecture, full text retrieval systems, inverted file databases, nonnumeric processing, pipelined networks, sorted list merging