Partitioned posting files: a parallel inverted file structure for information retrieval

ABSTRACT

This paper describes algorithms and data structures for applying a parallel computer to information retrieval. Previous work has described an implementation based on overlap encoded signatures. That system was limited by 1) the necessity of keeping the signatures in primary memory, and 2) the difficulties involved in implementing document-term weighting. Overcoming these limitations requires adapting the inverted index techniques used on serial machines. The most obvious adaptation, also previously described, suffers from the fact that data must be sent between processors at query-time. Since interprocessor communication is generally slower than local computation, this suggests that an algorithm which does not perform such communication might be faster. This paper presents a data structure, called a partitioned posting file, in which the interprocessor communication takes place at database-construction time, so that no data movement is needed at query-time. Algorithms for constructing the data structure are also described. Performance characteristics and storage overhead are established by benchmarking against a synthetic database.

REFERENCES

• 1: Craig Stanfill , Brewster Kahle, Parallel free-text search on the connection machine system, Communications of the ACM, v.29 n.12, p.1229-1239, Dec. 1986 [doi>10.1145/7902.7907]
• 2: Pogue, C. and P. WiUett, "'Use ofText Si grmtures for Document Retrieval in a Highly Parallel Environment," Parallel Computing Volume 4, 1987, pp. 259-268.
• 3: Harold S. Stone, Parallel querying of large databases: a case study, Computer, v.20 n.10, p.11-21, Oct. 1987 [doi>10.1109/MC.1987.1663384]
• 4: 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]
• 5: 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]
• 6: StanfilI, C., "'Parallel Computing for Information Retrieval: Recent Developments," Technical Report DR88--I, Thinking Machines Coxporation, Cambridge MA, January 1988.
• 7: C. Stanfill, Information retrieval using parallel signature files, Data Engineering, v.13 n.1, p.33-40, Mar. 1990
• 8: Salton, G., "Automatic Text Analysis," Science Volume 168, 1970, pp. 335-343.
• 9: Gerard Salton , Chris Buckley, Term Weighting Approaches in Automatic Text Retrieval, Cornell University, Ithaca, NY, 1987
• 10: C. Stanfill , R. Thau , D. Waltz, A parallel indexed algorithm for information retrieval, Proceedings of the 12th annual international ACM SIGIR conference on Research and development in information retrieval, p.88-97, June 25-28, 1989, Cambridge, Massachusetts, United States

INDEX TERMS

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

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

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

General Terms:
Algorithms, Design, Performance