The SIFT information dissemination system

ABSTRACT

Information dissemination is a powerful mechanism for finding information in wide-area environments. An information dissemination server accepts long-term user queries, collects new documents from information sources, matches the documents against the queries, and continuously updates the users with relevant information. This paper is a retrospective of the Stanford Information Filtering Service (SIFT), a system that as of April 1996 was processing over 40,000 worldwide subscriptions and over 80,000 daily documents. The paper describes some of the indexing mechanisms that were developed for SIFT, as well as the evaluations that were conducted to select a scheme to implement. It also describes the implementation of SIFT, and experimental results for the actual system. Finally, it also discusses and experimentally evaluates techniques for distributing a service such as SIFT for added performance and availability.

REFERENCES

• 1: Swarup Acharya , Michael J. Franklin , Stanley B. Zdonik, Disseminating Updates on Broadcast Disks, Proceedings of the 22th International Conference on Very Large Data Bases, p.354-365, September 03-06, 1996
• 2: D. Agrawal , A. El Abbadi, Exploiting logical structures in replicated databases, Information Processing Letters, v.33 n.5, p.255-260, January 1990 [doi>10.1016/0020-0190(90)90194-3]
• 3: BALABANOVIC, M. AND SHOHAM, Y. 1995. Learning information retrieval agents: Experiments with automated web browsing. In Proceedings of the 1995 AAAI Spring Symposium on Information Gathering from Heterogenous Distributed Environments (Stanford, CA, Mar.), AAAI Press, Menlo Park, CA.
• 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 , Alan F. Lewit, Optimization of inverted vector searches, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.97-110, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253515]
• 6: Shun Yan Cheung , Mostafa H. Ammar , Mustaque Ahamad, The Grid Protocol: A High Performance Scheme for Maintaining Replicated Data, Proceedings of the Sixth International Conference on Data Engineering, p.438-445, February 05-09, 1990
• 7: COHEN, D. 1992. A format for e-mailing bibliographical records. Tech. Rep. RFC-1357. DDN Network Information Center, SRI International, Menlo Park, CA.
• 8: DAO, S. AND PERRY, B. 1996. Information dissemination in hybrid satellite/terrestrial networks. IEEE Data Eng. Tech. Bull. 19, 3, 12-19.
• 9: FRANKLIN, M., Ed. 1996. Special issue on data dissemination. IEEE Data Eng. Tech. Bull. 19, 3, 3-54.
• 10: Peter W. Foltz , Susan T. Dumais, Personalized information delivery: an analysis of information filtering methods, Communications of the ACM, v.35 n.12, p.51-60, Dec. 1992 [doi>10.1145/138859.138866]
• 11: FRANKLIN, M. AND ZDONIK, S. 1996. Dissemination-based information systems. IEEE Data Eng. Tech. Bull. 19, 3, 20-30.
• 12: FRIEDBERG, S., INSEL, n., AND SPENCE, L. 1989. Linear Algebra. Prentice-Hall, Inc., Englewood Cliffs, NJ.
• 13: David K. Gifford , Robert W. Baldwin , Stephen T. Berlin , John M. Lucassen, An architecture for large scale information systems, Proceedings of the tenth ACM symposium on Operating systems principles, p.161-170, December 1985, Orcas Island, Washington, United States
• 14: GLANCE, D. 1996. Multicast support for data dissemination in orbixtalk. IEEE Data Eng. Tech. Bull. 19, 3, 31-39.
• 15: David Goldberg , David Nichols , Brian M. Oki , Douglas Terry, Using collaborative filtering to weave an information tapestry, Communications of the ACM, v.35 n.12, p.61-70, Dec. 1992 [doi>10.1145/138859.138867]
• 16: HARMON, D., Ed. 1993. Proceedings of the First Conference on Text Retrieval Conference.. National Institute of Standards and Technology, Gaithersburg, MD.
• 17: HARMAN, D. K., Ed. 1994. Proceedings of the 2nd Conference on Text Retrieval. (TREC-2). National Institute of Standards and Technology, Gaithersburg, MD.
• 18: HARMON, D., Ed. 1995. Proceedings of the 3rd Text Retrieval Conference. (TREC-3). National Institute of Standards and Technology, Gaithersburg, MD.
• 19: T. Imieliński , S. Viswanathan , B. R. Badrinath, Power efficient filtering of data on air, Proceedings of the 4th international conference on extending database technology on Advances in database technology, p.245-258, May 1994, Cambridge, United Kingdom
• 20: Ed Krol, The whole Internet user's guide and catalog, O'Reilly & Associates, Inc., Sebastopol, CA, 1992
• 21: Akhil Kumar, Hierarchical Quorum Consensus: A New Algorithm for Managing Replicated Data, IEEE Transactions on Computers, v.40 n.9, p.996-1004, September 1991 [doi>10.1109/12.83661]
• 22: LONG, D. D. E., CARROLL, J. L., AND PARK, C.J. 1991. A study of the reliability of Internet sites. In Proceedings of the l Oth IEEE Symposium on Reliable Distributed Systems (Pisa, Italy, Sept.), IEEE Press, Piscataway, NJ, 177-186.
• 23: Mamoru Maekawa, A N algorithm for mutual exclusion in decentralized systems, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.145-159, May 1985 [doi>10.1145/214438.214445]
• 24: Thomas W Malone , Kenneth R Grant , Franklyn A Turbak , Stephen A Brobst , Michael D Cohen, Intelligent information-sharing systems, Communications of the ACM, v.30 n.5, p.390-402, May 1987 [doi>10.1145/22899.22903]
• 25: MARIMBA, 1997. http://www.marimba.com. Marimba, Palo Alto, CA.
• 26: Brian Oki , Manfred Pfluegl , Alex Siegel , Dale Skeen, The Information Bus: an architecture for extensible distributed systems, ACM SIGOPS Operating Systems Review, v.27 n.5, p.58-68, Dec. 1993
• 27: 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
• 28: POINTCAST, 1997. http://www.pointcast.com. Pointcast, Sunnyvale, CA.
• 29: PORTER, M. F. 1980. An algorithm for suffix stripping. Program: Autom. Libr. Inf. Syst. 14, 3, 130-137.
• 30: Sampath Rangarajan , Sanjeev Setia , Satish K. Tripathi, A Fault-Tolerant Algorithm for Replicated Data Management, Proceedings of the Eighth International Conference on Data Engineering, p.230-237, February 03-07, 1992
• 31: Gerard. Salton, Automatic Information Organization and Retrieval., McGraw Hill Text, 1968
• 32: SALTON, G. 1991. Global text matching for information retrieval. Science 253, 1012-1015.
• 33: SHEKHAR, S., FETTERER, A., AND LIU, D. 1996. Genesis: An approach to data dissemination in advanced traveler information systems. IEEE Data Eng. Tech. Bull. 19, 3, 41-47.
• 34: SHETH, B. 1994. A learning approach to personalized information filtering. Master's Thesis. MIT Laboratory for Computer Science, Cambridge, MA.
• 35: Frank Curtis Stevens, Knowledge-based assistance for accessing large, poorly structured information spaces, University of Colorado at Boulder, Boulder, CO, 1993
• 36: TERRY, D. 1992. Replication in an information filtering system. In Proceedings of the 2nd Workshop on Management of Replicated Data (Monterey, CA, Nov.), 66-67.
• 37: Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979 [doi>10.1145/320071.320076]
• 38: Anthony Tomasic , Hector Garcia-Molina, Performance of inverted indices in shared-nothing distributed text document informatioon retrieval systems, Proceedings of the second international conference on Parallel and distributed information systems, p.8-17, January 1993, San Diego, California, United States
• 39: Stephen Wolfram, Mathematica: a system for doing mathematics by computer (2nd ed.), Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1991
• 40: H. P. Frei , M. F. Wyle, Retrieval algorithm effectiveness in a wide area network information filter, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.114-122, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122871]
• 41: Tak Woon Yan, Efficient techniques for wide-area information dissemination, Stanford University, Stanford, CA, 1996
• 42: YAN, T. AND GARCIA-MOLINA, H. 1993. Index structures for selective dissemination of information under the boolean model. Tech. Rep. STAN-CS-92-1454. Stanford University, Stanford, CA.
• 43: Tak W. Yan , Hector Garcia-Molina, Distributed selective dissemination of information, Proceedings of the third international conference on on Parallel and distributed information systems, p.89-98, October 1994, Autin, Texas, United States
• 44: 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
• 45: Tak W. Yan , Héctor García-Molina, Index structures for selective dissemination of information under the Boolean model, ACM Transactions on Database Systems (TODS), v.19 n.2, p.332-364, June 1994 [doi>10.1145/176567.176573]
• 46: Tak W. Yan , Hector Garcia-Molina, Duplicate Removal in Information System Dissemination, Proceedings of the 21th International Conference on Very Large Data Bases, p.66-77, September 11-15, 1995
• 47: YAN, T. W. AND GARC A-MOLINA, H. 1995. SIFT--a tool for wide-area information dissemination. In Proceedings of the 1995 Conference on USENIX Technical (Jan.), USENIX Assoc., Berkeley, CA, 177-186.
• 48: ZIPF, G. K. 1949. Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology. Addison-Wesley, Reading, MA.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

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

General Terms:
Algorithms, Performance

Keywords:
Boolean queries, dissemination, filtering, indexing, vector space queries