Article ID Journal Published Year Pages File Type
397574 Information Systems 2008 25 Pages PDF
Abstract

Various approaches for keyword search in different settings (e.g., relational databases and XML) actually deal with the problem of enumerating K-fragments. For a given set of keywords K, a K-fragment is a subtree T of the given data graph, such that T contains all the keywords of K and no proper subtree of T has this property. There are three types of K-fragments: directed, undirected and strong. This paper describes efficient algorithms for enumerating K-fragments. Specifically, for all three types of K-fragments, algorithms are given for enumerating all K-fragments with polynomial delay and polynomial space. It is shown how these algorithms can be enhanced to enumerate K-fragments in a heuristic order. For directed K-fragments and acyclic data graphs, an algorithm is given for enumerating with polynomial delay in the order of increasing weight (i.e., the ranked order), assuming that K is of a fixed size.

Related Topics
Physical Sciences and Engineering Computer Science Artificial Intelligence
Authors
, ,