Abstract Matching Algorithms for User Notification

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 three directions: (a) definition of a formal model for the publish/subscribe process; (b) introduction of a semi-lattice structure on subscriptions allowing the filtering out of non matching subscriptions; (c) experimental results that show the cost benefits obtained by our approach.