eCite Digital Repository

Fast result enumeration for keyword queries on XML data


Zhou, J and Bao, Z and Chen, Z and Ling, TW, Fast result enumeration for keyword queries on XML data, Database Systems for Advanced Applications Part I, 15-18 April 2012, Busan, South Korea, pp. 95-109. ISBN 978-3-642-29037-4 (2012) [Refereed Conference Paper]

Copyright Statement

Copyright 2012 Springer

DOI: doi:10.1007/978-3-642-29038-1_9


In this paper, we focus on efficient construction of tightest matched subtree (TMSubtree) results for keyword queries on XML data based on SLCA semantics, where "matched" means that all nodes in a returned subtree satisfy the constraint that the set of distinct keywords of the subtree rooted at each node is not subsumed by that of any of its sibling node, while "tightest" means that no two subtrees rooted at two sibling nodes can contain the same set of keywords. Assume that d is the depth of a given TMSubtree, m is the number of keywords of a given query Q, we proved that if dm, a matched subtree result has at most 2m! nodes; otherwise, the size of a matched subtree result is bounded by (dm+2)m!. Based on this theoretical result, we propose a pipelined algorithm to construct TMSubtree results without rescanning all node labels. Experiments verify the benefits of our algorithm in aiding keyword search over XML data.

Item Details

Item Type:Refereed Conference Paper
Keywords:keyword query, result enumeration, XML
Research Division:Information and Computing Sciences
Research Group:Data management and data science
Research Field:Data management and data science not elsewhere classified
Objective Division:Information and Communication Services
Objective Group:Information systems, technologies and services
Objective Field:Information systems, technologies and services not elsewhere classified
UTAS Author:Bao, Z (Dr Zhifeng Bao)
ID Code:92182
Year Published:2012
Deposited By:Information and Communication Technology
Deposited On:2014-06-09
Last Modified:2015-03-25

Repository Staff Only: item control page