eCite Digital Repository

Fast SLCA and ELCA computation for XML keyword queries based on set intersection


Zhou, J and Bao, Z and Wang, W and Ling, TW and Chen, Z and Lin, X and Guo, J, Fast SLCA and ELCA computation for XML keyword queries based on set intersection, Proceedings of the IEEE 28th International Conference on Data Engineering, 1-5 April 2012, Washington DC, USA, pp. 905-916. ISBN 978-1-4673-0042-1 (2012) [Refereed Conference Paper]

Copyright Statement

Copyright 2012 IEEE

DOI: doi:10.1109/ICDE.2012.75


In this paper, we focus on efficient keyword query processing for XML data based on SLCA and ELCA semantics. We propose for each keyword a novel form of inverted list, which includes IDs of nodes that directly or indirectly contain the keyword. We propose a family of efficient algorithms that are based on the set intersection operation for both semantics. We show that the problem of SLCA/ELCA computation becomes finding a set of nodes that appear in all involved inverted lists and satisfy certain conditions. We also propose several optimization techniques to further improve the query processing performance. We have conducted extensive experiments with many alternative methods. The results demonstrate that our proposed methods outperform existing ones by up to two orders of magnitude in many cases.

Item Details

Item Type:Refereed Conference Paper
Keywords:database indexing, XML, keyword query
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:92184
Year Published:2012
Web of Science® Times Cited:14
Deposited By:Information and Communication Technology
Deposited On:2014-06-09
Last Modified:2015-02-12

Repository Staff Only: item control page