Fax: +81-011-706-7682Keyword Query Processing Using Binary Decision Diagrams under a Taxonomy Model

(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. In this paper, we present a novel method of processing such keyword queries. Our method is based on Binary Decision Diagram (BDD), an efficient data structure for manipulating large-scale Boolean functions. We compile the given keyword queries into a BDD under a taxonomy model. The number of possible keyword sets can be exponentially large, but the compiled BDD gives a compact representation, and matching process will become faster. In addition, our method can deal with any Boolean combination of keywords from the taxonomy, while our previous result considered only a conjunctive keyword set. In this paper, we describe the basic idea of our new method and show a preliminary experimental result. 1