Fast SLCA and ELCA Computation for XML Keyword Query Based on Set Intersection Operation
No Thumbnail Available
Date
2011-07-21T08:22:45Z
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In this paper, we focus on efficient keyword query processing on XML data based on SLCA and ELCA semantics. We have an elaborate design of the keyword inverted list to efficiently locate the nodes that directly or indirectly contain a given keyword. We propose a family of algorithms that are based on set intersection operation to accelerate SLCA and ELCA computation. In essence,
the problem of SLCA and ELCA computation becomes finding a set of common nodes that appear in all inverted lists and checking their satisfiability. We show that any existing set intersection algorithms can be adopted for SLCA and ELCA computation, and our optimization techniques can be used together with any existing search method to improve the overall performance. Experiments verify that the performance of our methods outperforms existing methods by more than 2 orders of magnitude in most cases.