File(s) under permanent embargo

Fast ELCA computation for keyword queries on XML data

conference contribution
posted on 2010-01-01, 00:00 authored by R Zhou, C Liu, Jianxin LiJianxin Li
Keyword search is integrated in many applications on account of the convenience to convey users' query intention. Recently, answering keyword queries on XML data has drawn the attention of web and database communities, because the success of this research will relieve users from learning complex XML query languages, such as XPath/XQuery, and/or knowing the underlying schema of the queried XML data. As a result, information in XML data can be discovered much easier. To model the result of answering keyword queries on XML data, many LCA (lowest common ancestor) based notions have been proposed. In this paper, we focus on ELCA (Exclusive LCA) semantics, which is first proposed by Guo et al. and afterwards named by Xu and Papakonstantinou. We propose an algorithm named Hash Count to find ELCAs efficiently. Our analysis shows the complexity of Hash Count algorithm is O(kd|S1|), where k is the number of keywords, d is the depth of the queried XML document and |S1| is the frequency of the rarest keyword. This complexity is the best result known so far. We also evaluate the algorithm on a real DBLP dataset, and compare it with the state-of-the-art algorithms. The experimental results demonstrate the advantage of Hash Count algorithm in practice.



Association for Computing Machinery. Conference (13th : 2010 : Lausanne, Switzerland)


Association for Computing Machinery Conference


549 - 560


Association for Computing Machinery


Lausanne, Switzerland

Place of publication

New York, N.Y.

Start date


End date






Publication classification

E1.1 Full written paper - refereed

Copyright notice

2010, ACM


I Manolescu, S Spaccapietra, J Teubner, M Kitsuregawa, A Leger, F Naumann, A Ailamaki, F Ozcan

Title of proceedings

EDBT 2010 : Proceedings of the 13th International Conference on Extending Database Technology

Usage metrics