Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.3/85990

Download PDF (Accepted manuscript) (Adobe Acrobat PDF, -1 bytes)

Title

Fast ELCA computation for keyword queries on XML data

Author(s)

Zhou, Rui;  Liu, Chengfei;  Li, Jianxin

Abstract

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.

Publication type

Conference paper

Research centre

Swinburne University of Technology. Faculty of Information and Communication Technologies

Source

Advances in Database Technology: proceedings of the 13th International Conference on Extending Database Technology (EDBT 2010), Lausanne, Switzerland, 22-26 March 2010 / Ioana Manolescu, Stefano Spaccapietra, Jens Teubner, Masaru Kitsuregawa, Alain Leger, Felix Naumann, Anastasia Ailamaki and Fatma Ozcan (eds.), Vol. 426, pp. 549-560

Publication year

2010

FOR Code(s)

0804 Data Format

Keyword(s)

ELCA;  Exclusive LCA semantics;  Keyword query;  Keyword searches;  XML

Publisher

ACM

ISBN

9781605589459, 1605589454

Publisher URL

http://dx.doi.org/10.1145/1739041.1739107

Copyright

Copyright © ACM, 2010. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of EDBT (2010) http://doi.acm.org/10.1145/1739041.1739107

Research Projects

XML views of relational databases: semantics and update problems, Australian Research Council grant number DP878405

Full text

Peer reviewed