The design of a high performance information filtering system

ABSTRACT

A high performance information filtering system has three main requirements: it must be effective in supplying users with useful information, it must do so in a timely fashion, and it must be able to handle a large throughput of information and a large number of user profiles efficiently. These three requirements pose a difficult problem, and to our knowledge no existing system is capable of meeting all three. In this paper we describe a system which combines a number of techniques from other information retrieval and filtering systems, and is capable of providing high performance on a typical workstation platform. We provide estimates of computing resource usage, and show that our system is also scalable.

REFERENCES

• 1: Nicholas J. Belkin , W. Bruce Croft, Retrieval techniques, Annual review of information science and technology, vol. 22, Elsevier Science Inc., New York, NY, 1987
• 2: Nicholas J. Belkin , W. Bruce Croft, Information filtering and information retrieval: two sides of the same coin?, Communications of the ACM, v.35 n.12, p.29-38, Dec. 1992 [doi>10.1145/138859.138861]
• 3: Timothy C. Bell , Alistair Moffat , Ian H. Witten , Justin Zobel, The MG retrieval system: compressing for space and speed, Communications of the ACM, v.38 n.4, p.41-42, April 1995 [doi>10.1145/205323.205327]
• 4: Eric W. Brown, Fast evaluation of structured queries for information retrieval, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.30-38, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215329]
• 5: Chris Buckley , Gerard Salton , James Allan, The effect of adding relevance information in a relevance feedback environment, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.292-300, July 03-06, 1994, Dublin, Ireland
• 6: Buckley, C., Salton, G., Allan, J., and Singhal, A. {1994b}. Automatic query expansion using SMART: TREC 3. In Harman, D., editor, Proc. Third Text Retrieval Conference (TREC-3), pages 69-80, Gaithersburg, MD. National Institute of Standards and Technology.
• 7: Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, August 1994
• 8: Donna Harman, Relevance feedback and other query modification techniques, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 9: Harman, D. {1994}. Overview of the third text retrieval conference (TREC-3). In Harman, D., editor, Proc. Third Text Retrieval Conference (TREC-3), pages 1-20, Gaithersburg, MD. National Institute of Standards and Technology.
• 10: Harman, D. and Candela, G. {1990}. Retrieving records from a gigabyte of text on a minicomputer using statistical ranking. Journal of the American Society for Information Science, 41(8):581-589.
• 11: Donna Harman , R. Baeza-Yates , Edward Fox , W. Lee, Inverted files, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 12: David Hull, Improving text retrieval for the routing problem using latent semantic indexing, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.282-291, July 03-06, 1994, Dublin, Ireland
• 13: Alistair Moffat , Timothy A. H. Bell, In situ generation of compressed inverted files, Journal of the American Society for Information Science, v.46 n.7, p.537-550, Aug. 1995 [doi>10.1002/(SICI)1097-4571(199508)46:7<537::AID-ASI7>3.0.CO;2-P]
• 14: Alistair Moffat , Justin Zobel, Self-indexing inverted files for fast text retrieval, ACM Transactions on Information Systems (TOIS), v.14 n.4, p.349-379, Oct. 1996 [doi>10.1145/237496.237497]
• 15: Michael Persin, Document filtering for fast ranking, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.339-348, July 03-06, 1994, Dublin, Ireland
• 16: Reid, B. {1995}. USENET readership summary report for Jul 95. USENET Newsgroup news.lists.
• 17: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 18: Salton, G. and Buckley, C. {1990}. Improving retrieval performance by relevance feedback. Journal of the Amemcan Society for Informatwn Science, 41(4):288-297.
• 19: Gerard Salton , Edward A. Fox , Harry Wu, Extended Boolean information retrieval, Communications of the ACM, v.26 n.11, p.1022-1036, Nov. 1983 [doi>10.1145/182.358466]
• 20: Robert Sedgewick, Algorithms in C, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 21: Kurt Shoens , Anthony Tomasic , Héctor García-Molina, Synthetic workload performance analysis of incremental updates, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.329-338, July 03-06, 1994, Dublin, Ireland
• 22: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 23: Tak W. Yan , Hector Garcia-Molina, Index Structures for Information Filtering Under the Vector Space Model, Proceedings of the Tenth International Conference on Data Engineering, p.337-347, February 14-18, 1994
• 24: Zipf, G.K. {1949}. Human Behavior and the Pmnciple of Least Effort. Addison-Wesley.

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.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Design, Experimentation, Performance