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

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

Title

Matching top-k answers of twig patterns in probabilistic XML

Author(s)

Ning, Bo;  Liu, Chengfei;  Yu, Jeffrey Xu;  Wang, Guoren;  Li, Jianxin

Abstract

The flexibility of XML data model allows a more natural representation of uncertain data compared with the relational model. The top-k matching of a twig pattern against probabilistic XML data is essential. Some classical twig pattern algorithms can be adjusted to process the probabilistic XML. However, as far as finding answers of the top-k probabilities is concerned, the existing algorithms suffer in performance, because many unnecessary intermediate path results, with small probabilities, need to be processed. To cope with this problem, we propose a new encoding scheme called PEDewey for probabilistic XML in this paper. Based on this encoding scheme, we then design two algorithms for finding answers of top-k probabilities for twig queries. One is called ProTJFast, to process probabilistic XML data based on element streams in document order, and the other is called PTopKTwig, based on the element streams ordered by the path probability values. Experiments have been conducted to study the performance of these algorithms.

Publication type

Conference paper

Research centre

Swinburne University of Technology

Source

Lecture notes in computer science: Proceedings of the 15th International Conference on Database Systems for Advanced Applications (DASFAA 2010), Tsukuba, Japan, 01-04 April 2010 / Hiroyuki Kitagawa, Yoshiharu Ishikawa, Qing Li and Chiemi Watanabe (eds.), Vol. 5981, pp. 125-139

Publication year

2010

FOR Code(s)

0804 Data Format

Keyword(s)

Algorithms;  Data;  Probabilistic XML;  Top-k matching;  Twig patterns;  XML

Publisher

Springer

ISSN

0302-9743 (series ISSN)

ISBN

9783642120251, 3642120253

Publisher URL

http://dx.doi.org/10.1007/978-3-642-12026-8_12

Copyright

Copyright © Springer-Verlag Berlin Heidelberg 2010. 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.

Research Projects

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

Full text

Peer reviewed