Parallel text searching in serial files using a processor farm

ABSTRACT

This paper discusses the implementation of a parallel text retrieval system using a microprocessor network. The system is designed to allow fast searching in document databases organised using the serial file structure, with a very rapid initial text signature search being followed by a more detailed, but more time-consuming, pattern matching search. The network is built from transputers, high performance microprocessors developed specifically for the construction of highly parallel computing systems, which are linked together in a processor farm. The paper discusses the design and implementation of processor farms, and then reports our initial studies of the efficiency of searching that can be achieved using this approach to text retrieval from serial files.

REFERENCES

• 1: Amdahl, G. (1967). The validity of the single processor approach to achieving large scale computing capabilities. AFIPS Conference Proceedings, 30, 483-485.
• 2: William C. Athas , Charles L. Seitz, Multicomputers: Message-Passing Concurrent Computers, Computer, v.21 n.8, p.9-24, August 1988 [doi>10.1109/2.73]
• 3: Carroll, D.M., Pogue, C.A. # Willett, P. (1988). Bibliographic pattern matching using the ICL Distributed Array Preceder. Journal of the American Society.for Information Science, 39, 390-399.
• 4: J. K. Cringean , G. A. Manson , P. Wilett , G. A. Wilson, Efficiency of text scanning in bibliographic databases using microprocessor-based, multiprocessor networks, Journal of Information Science, v.14 n.6, p.335-345, July 1988 [doi>10.1177/016555158801400604]
• 5: Cringean, J.K., Lynch, M.F., Martson, G.A., Willett, P. & Wilson, G.A. (1989a). Parallel processing techniques for information retrieval. Searching of textual and chemical databaaes using tremsputer networks. Proceedings of the Thirteenth International Online Information Meeting, 447-462.
• 6: Cringean, J.K., England, R.., Manson, G.A. & Willett, P. (1989b). Best Match Searchin9 in Document Retrieval Systems Using 73#nsputer Networks. London: British Library Reoearch and Development Department.
• 7: Cringean, J.K., England, R., Manson, G.A. & Willett, P. (1990). Implementation of text scanning using a multicomputer network. Part I. System design. Submitted for publication.
• 8: W. Bruce Croft , Pasquale Savino, Implementing ranking strategies using text signatures, ACM Transactions on Information Systems (TOIS), v.6 n.1, p.42-62, Jan. 1988 [doi>10.1145/42279.45947]
• 9: Michel, Dubois , Christoph Scheurich , Fayé A. Briggs, Synchronization, Coherence, and Event Ordering in Multiprocessors, Computer, v.21 n.2, p.9-21, February 1988 [doi>10.1109/2.15]
• 10: Chris Faloutsos, Access methods for text, ACM Computing Surveys (CSUR), v.17 n.1, p.49-74, March 1985 [doi>10.1145/4078.4080]
• 11: Flynn, M.J. (1972). Some computer organisations and their effectiveness. IEEE Thansactions on Computers, C-P1, 948-960.
• 12: Geoffrey C. Fox , Mark A. Johnson , Gregory A. Lyzenga , Steve W. Otto , John K. Salmon , David W. Walker, Solving problems on concurrent processors. Vol. 1: General techniques and regular problems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 13: Gajski, D.D. & Peir, J.K. (1985). Essential issues in multiproeessor systems. Computer, 9-27.
• 14: John L. Gustafson, Reevaluating Amdahl's law, Communications of the ACM, v.31 n.5, p.532-533, May 1988 [doi>10.1145/42411.42415]
• 15: Handler, W. (1977). The impact of classification schemes on computer architectures. In Proceedings of the 1977 lntermational Conference on Parallel Processing (pp. 7-15). New York: IEEE.
• 16: Hey, A.J.G. (1988). Reconfigurable transpute~ networks: practical concurrent computation. Proceedings of the Royal Society, A326, 395-410.
• 17: R. W. Hockney , C. R. Jesshope, Parallel Computers Two: Architecture, Programming and Algorithms, IOP Publishing Ltd., Bristol, UK, 1988
• 18: Horspool, R.N. (1980). Practical fast matching in strings. Software - Practice and Experience, 10, 501-506.
• 19: May, D. & Taylor, R. (1984). occma- an overview. Microprocessors and Microsystems, 8, 73-79-
• 20: K C Mohan , P Willett, Nearest neighbour searching in serial files using text signature, Journal of Information Science, v.11 n.1, p.31-39, 1985 [doi>10.1177/016555158501100105]
• 21: Patton, P.C. (1985). Multiprocessors: architecture and applications. Computer, 18(6), 29-40.
• 22: D J Pritchard , C R Askew , D B Carpenter , I Glendinning , A J G Hey , D A Nicole, Practical parallelism using transputer arrays, Volume I: Parallel architectures on PARLE: Parallel Architectures and Languages Europe, p.278-294, March 1987, Eindhoven, The Netherlands
• 23: Michael J. Quinn, Designing efficient algorithms for parallel computers, McGraw-Hill, Inc., New York, NY, 1987
• 24: Daniel A. Reed , Richard M. Fujimoto, Multicomputer networks: message-based parallel processing, MIT Press, Cambridge, MA, 1988
• 25: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 26: Gerard Salton , Chris Buckley, Parallel text search methods, Communications of the ACM, v.31 n.2, p.202-215, Feb. 1988 [doi>10.1145/42372.42380]
• 27: R. Sharma, A generic machine for parallel information retrieval, Information Processing and Management: an International Journal, v.25 n.3, p.223-235, May 1989 [doi>10.1016/0306-4573(89)90041-1]
• 28: Shore, J.E. (1973). Second thoughts on parallel processing. Computers and Electrical Engineering, 1# 95-109..
• 29: David B. Skillicorn, A Taxonomy for Computer Architectures, Computer, v.21 n.11, p.46-57, November 1988 [doi>10.1109/2.86786]
• 30: Mark Stewart , Peter Willett, Nearest neighbour searching in binary search trees: Simulation of a multiprocessor system, Journal of Documentation, v.43 n.2, p.93-111, June 1987 [doi>10.1108/eb026803]
• 31: Marina Waldén , Kaisa Sere, Free text retrieval on transputer networks, Microprocessors & Microsystems, v.13 n.3, p.179-187, April 1989 [doi>10.1016/0141-9331(89)90124-5]
• 32: Waltz, D., Stanfill, C., Smith, S. & Thau, R. (1987). Very large database applications of the Connection Machine system. AFIPS Conference Proceedings, 56, 159-165.
• 33: Willett, P. & Rasmussen, E.M. (1990). Parallel Database Processing. Text Retrieval and Cluster Analysis using the Distributed Array Processor. London" Pitman.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.3 Microcomputers

          Nouns: INMOS Transputer

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance