Top-Down XML Keyword Query Processing

Abstract

Efficiently answering XML keyword queries has attracted much research effort in the last decade. The key factors resulting in the inefficiency of existing methods are the <i>common-ancestor-repetition</i> (CAR) and <i>visiting-useless-nodes</i> (VUN) problems. To address the CAR problem, we propose a <i>generic </i> <i>top-down</i> processing strategy to answer a given keyword query w.r.t. LCA/SLCA/ELCA semantics. By “ <i>top-down</i> ”, we mean that we visit all <i>common ancestor</i> (CA) nodes in a depth-first, left-to-right order; by “ <i>generic</i> ”, we mean that our method is independent of the query semantics. To address the VUN problem, we propose to use child nodes, rather than descendant nodes to test the satisfiability of a node <inline-formula><tex-math notation="LaTeX">$v$</tex-math></inline-formula> w.r.t. the given semantics. We propose two algorithms that are based on either traditional inverted lists or our newly proposed LLists to improve the overall performance. We further propose several algorithms that are based on hash search to simplify the operation of finding CA nodes from all involved LLists. The experimental results verify the benefits of our methods according to various evaluation metrics.