BDD-Based Combinatorial Keyword Query Processing under a Taxonomy Model

BDD-Based Combinatorial Keyword Query Processing under a Taxonomy Model

Shin-ichi Minato, Nicolas Spyratos
Copyright: © 2012 |Pages: 11
DOI: 10.4018/ijoci.2012100104
OnDemand:
(Individual Articles)
Available
$37.50
Current Special Offers
No Current Special Offers
TOTAL SAVINGS: $37.50

Abstract

Digital libraries are one of the key systems for an IT society, and supporting easy access to them is an important technical issue between a human and an intelligent system. Here the authors 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 chapter, the authors present a novel method of processing such keyword queries. Their method is based on Binary Decision Diagram (BDD), an efficient data structure for manipulating large-scale Boolean functions. The authors 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 enabling a highly efficient matching process. In addition, the authors' method can deal with any Boolean combination of keywords from the taxonomy, while the previous result considered only a conjunctive keyword set. In this chapter, they describe the basic idea of their new method, and then the authors show their preliminary experimental result applying to a document set with large-scale keyword domain under a real-life taxonomy structure.
Article Preview
Top

Preliminaries

Here we describe the basic framework of subscription-notification service which we consider in this paper.

Subscription-Notification Service in Digital Library

Figure 1 shows the basic processing flow of our system. A document is represented in the digital library repository by a description of its content together with an identifier (say, the document's URI) allowing to access the document's content. A number of documents are incoming to the digital library every day, and the identifier list of recent new documents is notified to each user periodically (daily, weekly, or monthly). Each user can specify a subscription to show the composed keywords that are of interest to that user. Every document has a description with a set of keywords, and if one of the keywords matches to some users' subscriptions, the identifier of the document is added to the notification list. Here, we assume that a user's subscription is not so frequently updated as the notification periods.

Figure 1.

Basic processing flow of subscription-notification service

ijoci.2012100104.f01

If we consider a nation-wide digital library system, the number of documents and the number of users become quite huge, and it is an important problem to reduce the computation cost for matching (or filtering) of the documents to each user.

Complete Article List

Search this Journal:
Reset
Volume 13: 1 Issue (2023)
Volume 12: 4 Issues (2022)
Volume 11: 4 Issues (2021)
Volume 10: 4 Issues (2020)
Volume 9: 4 Issues (2019)
Volume 8: 4 Issues (2018)
Volume 7: 4 Issues (2017)
Volume 6: 4 Issues (2016)
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing