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

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

Title

ELCA evaluation for keyword search on probabilistic XML data

Author(s)

Zhou, Rui;  Liu, Chengfei;  Li, Jianxin;  Yu, Jeffrey Xu

Abstract

As probabilistic data management is becoming one of the main research focuses and keyword search is turning into a more popular query means, it is natural to think how to support keyword queries on probabilistic XML data. With regards to keyword query on deterministic XML documents, ELCA (Exclusive Lowest Common Ancestor) semantics allows more relevant fragments rooted at the ELCAs to appear as results and is more popular compared with other keyword query result semantics (such as SLCAs). In this paper, we investigate how to evaluate ELCA results for keyword queries on probabilistic XML documents. After defining probabilistic ELCA semantics in terms of possible world semantics, we propose an approach to compute ELCA probabilities without generating possible worlds. Then we develop an efficient stack-based algorithm that can find all probabilistic ELCA results and their ELCA probabilities for a given keyword query on a probabilistic XML document. Finally, we experimentally evaluate the proposed ELCA algorithm and compare it with its SLCA counterpart in aspects of result probability, time and space efficiency, and scalability.

Publication type

Journal article

Research centre

Swinburne University of Technology. Faculty of Information and Communication Technologies

Source

World Wide Web, Vol. 16, no. 2 (Mar 2013), pp. 171-193

Publication year

2013

FOR Code(s)

0805 Distributed Computing;  0806 Information Systems

Keyword(s)

ELCA;  Exclusive Lowest Common Ancestor;  Keyword searches;  Probabilistic data management;  Queries;  Searches;  Uncertain data;  XML

Publisher

Springer

ISSN

1386-145X

Publisher URL

http://dx.doi.org/10.1007/s11280-012-0166-4

Copyright

Copyright © Springer Science+Business Media, LLC 2012. The accepted manuscript is reproduced in accordance with the copyright policy of the publisher. The definitive version of the publication is available at www.springer.com.

Full text

Peer reviewed