Call for Papers
About the Journal
Editorial Board
Publication Ethics
Instructions for Authors
Current Issue
Back Issues
Search for Articles
Back Issues

JCSE, vol. 6, no. 2, pp.127-140, June, 2012


Fast Result Enumeration for Keyword Queries on XML Data

Junfeng Zhou, Ziyang Chen, Xian Tang, Zhifeng Bao, TokWang Ling
School of Information Science and Engineering, Yanshan University, Qinhuangdao, China/ School of Economics and Management, Yanshan University, Qinhuangdao, China/ School of Computing, National University of Singapore, Singapore

Abstract: In this paper, we focus on efficient construction of tightest matched subtree (TMSubtree) results, for keyword queries on extensible markup language (XML) data, based on smallest lowest common ancestor (SLCA) semantics. Here, “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 nodes, 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 d ≤ m, a matched subtree result has at most 2m! nodes; otherwise, the size of a matched subtree result is bounded by (d ? m + 2)m!. Based on this theoretical result, we propose a pipelined algori

Keyword: XML; Keyword search; Result enumeration

Full Paper:   111 Downloads, 2314 View

ⓒ Copyright 2010 KIISE – All Rights Reserved.    
Korean Institute of Information Scientists and Engineers (KIISE)   #401 Meorijae Bldg., 984-1 Bangbae 3-dong, Seo-cho-gu, Seoul 137-849, Korea
Phone: +82-2-588-9240    Fax: +82-2-521-1352    Homepage:    Email: