Efficient query processing for XML keyword queries based on the IDList index

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...

Full description

Saved in:
Bibliographic Details
Published in:The VLDB journal 2014-02, Vol.23 (1), p.25-50
Main Authors: Zhou, Junfeng, Bao, Zhifeng, Wang, Wei, Zhao, Jinjia, Meng, Xiaofeng
Format: Article
Language:English
Subjects:
Applied sciences
Computer Science
Computer science
control theory
systems
Data processing. List processing. Character string processing
Database Management
Exact sciences and technology
Information retrieval. Graph
Information systems. Data bases
Memory organisation. Data processing
Regular Paper
Software
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 common-ancestor-repetition problem. In this paper, we propose a novel form of inverted list, namely the IDList ; the IDList for keyword consists of ordered nodes that directly or indirectly contain . 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.
ISSN:1066-8888
0949-877X
DOI:10.1007/s00778-013-0313-2