User notification in taxonomy based digital libraries

ABSTRACT

We consider a publish/subscribe system for digital libraries which continuously evaluates queries over a large repository containing document descriptions. The subscriptions, the query expressions and the document descriptions, all rely on a taxonomy that is a hierarchically organized set of keywords, or terms. The digital library supports insertion, update and removal of a document. Each of these operations is seen as an event that must be notified only to those users whose subscriptions match the document's description. The paper addresses the problem of efficiently supporting the notification process, and makes contributions in two directions: (a) definition of a formal model for the publish/subscribe process; (b) proposal of a semi-lattice structure for subscriptions allowing the filtering out of non matching subscriptions. Experimental results that show the cost benefits obtained by our approach are presented in the full paper [6]

REFERENCES

• 1: The ACM computing classification system, 1999. www.acm.org/class.
• 2: R. Agrawal , A. Borgida , H. V. Jagadish, Efficient management of transitive relationships in large data and knowledge bases, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.253-262, June 1989, Portland, Oregon, United States
• 3: Marcos K. Aguilera , Robert E. Strom , Daniel C. Sturman , Mark Astley , Tushar D. Chandra, Matching events in a content-based subscription system, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.53-61, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301326]
• 4: A.V. Aho, M.R.Garey, and J.D. Ullman. The Transitive Reduction of a Directed Graph. Society for Industrial and Applied Mathematics (SIAM), 1(2):131--137, 1972.
• 5: Mikhail J. Atallah , Susan Fox , Suzanne Lassandro, Algorithms and Theory of Computation Handbook, CRC Press, Inc., Boca Raton, FL, 1998
• 6: H. BelhajFrej, P. Rigaux, and N. Spyratos. Matching algorithms for user notification in digital libraries, 2006. http://www.lri.fr/ hanen/MatchingAlgorithms.pdf.
• 7: Alexis Campailla , Sagar Chaki , Edmund Clarke , Somesh Jha , Helmut Veith, Efficient filtering in publish-subscribe systems using binary decision diagrams, Proceedings of the 23rd International Conference on Software Engineering, p.443-452, May 12-19, 2001, Toronto, Ontario, Canada
• 8: Vassilis Christophides , Dimitris Plexousakis , Michel Scholl , Sotirios Tourtounis, On labeling schemes for the semantic web, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775230]
• 9: A.J. Demers, J. Gehrke, M. Hong, M. Riedewald, and W.M. White. Towards expressive publish/subscribe systems. In Intl Conf. on Extending Database Technology (EDBT), pages 627--644, 2006.
• 10: Yanlei Diao , Mehmet Altinel , Michael J. Franklin , Hao Zhang , Peter Fischer, Path sharing and predicate evaluation for high-performance XML filtering, ACM Transactions on Database Systems (TODS), v.28 n.4, p.467-516, December 2003 [doi>10.1145/958942.958947]
• 11: Françoise Fabret , H. Arno Jacobsen , François Llirbat , Joăo Pereira , Kenneth A. Ross , Dennis Shasha, Filtering algorithms and implementation for very fast publish/subscribe systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.115-126, May 21-24, 2001, Santa Barbara, California, United States
• 12: J. Gough and G. Smith. Efficient recognition of events in a distributed system. In Proc. Australasian Computer Science Conference, 1995.
• 13: João Pereira , Françoise Fabret , François Llirbat , Radu Preotiuc-Pietro , Kenneth A. Ross , Dennis Shasha, Publish/Subscribe on the Web at Extreme Speed, Proceedings of the 26th International Conference on Very Large Data Bases, p.627-630, September 10-14, 2000
• 14: Milenko Petrovic , Haifeng Liu , Hans-Arno Jacobsen, G-ToPSS: fast filtering of graph-based metadata, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060824]
• 15: P. Rigaux and N. Spyratos. Metadata Inference for Document Retrieval in a Distributed Repository. In ASIAN'04, 2004.
• 16: T.W. Yan and H. Garcia-Molina. SIFT-A tool for wide-area information dissemination. In Proc. of USENIX Technical Conference, pages 177--186, 1995.
• 17: Tak W. Yan , Hector Garcia-Molina, The SIFT information dissemination system, ACM Transactions on Database Systems (TODS), v.24 n.4, p.529-565, Dec. 1999 [doi>10.1145/331983.331992]

INDEX TERMS

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

General Terms:
Algorithms, Languages, Performance, Theory

Keywords:
digital libraries, matching algorithms, personalization, publish/subscribe systems, user notification