Top-Down XML Keyword Query Processing

Junfeng Zhou

doi:10.1109/TKDE.2016.2516536

Top-Down XML Keyword Query Processing

2016-05-01

8

PRE

AI

DOI：10.1109/TKDE.2016.2516536

原文链接

原文求助

摘要

En 中文

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 common-ancestor-repetition (CAR) and visiting-useless-nodes (VUN) problems. To address the CAR problem, we propose a generic top-down processing strategy to answer a given keyword query w.r.t. LCA/SLCA/ELCA semantics. By top-down, we mean that we visit all common ancestor (CA) nodes in a depth-first, left-to-right order; by generic, 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 v 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.

Keyword:

XML

keyword search

LCA

LList

Top-Down XML Keyword Query Processing

摘要

AI总结

期刊

机构