Keyword search over XML data has attracted a lot of research efforts in the last decade, where one of the fundamental research problems is how to efficiently answer a given keyword query w.r.t. a certain query semantics. We found that the key factor resulting in the inefficiency for existing methods is that they all heavily suffer from the commonancestor- repetition problem. In this paper, we propose a novel form of inverted list, namely the IDList; the IDList for keyword k consists of ordered nodes that directly or indirectly contain k. We then show that finding keyword query results based on the smallest lowest common ancestor and exclusive lowest common ancestor semantics can be reduced to ordered set intersection problem, which has been heavily optimized due to its application in areas such as information retrieval and database systems. We propose several algorithms that exploit set intersection in different directions and with or without using additional indexes.We further propose several algorithms that are based on hash search to simplify the operation of finding common nodes from all involved IDLists. We have conducted an extensive set of experiments using many state-of-the-art algorithms and several large-scale datasets. The results demonstrate that our proposed methods outperform existing methods by up to two orders of magnitude in many cases.

Item Type:	Refereed Article
Keywords:	xml keyword search, set intersection
Research Division:	Information and Computing Sciences
Research Group:	Information Systems
Research Field:	Database Management
Objective Division:	Information and Communication Services
Objective Group:	Computer Software and Services
Objective Field:	Information Processing Services (incl. Data Entry and Capture)
Author:	Bao, Z (Dr Zhifeng Bao)
ID Code:	90346
Year Published:	2014
Web of Science® Times Cited:	11
Deposited By:	Information and Communication Technology
Deposited On:	2014-03-31
Last Modified:	2014-08-11
Downloads:	0