TCS-TR-A-07-28

Date: Thu Aug 9 18:09:16 2007

Title: Keyword Query Processing Using Binary Decision Diagrams under a Taxonomy Model

Authors: Shin-ichi Minato and Nicolas Spyratos

Contact:

  • First name: Shin-ichi
  • Last name: Minato
  • Address: Division of Computer Science, Hokkaido Univ. North 14 West 9, Sapporo, 060-0814 Japan
  • Email: minato@ist.hokudai.ac.jp

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.


©Copyright 2007 Authors