Efficiently Subtree Matching between XML and Probabilistic XML Documents

Abstract:

We explored the subtree matching problem of probabilistic XML documents: finding the matches of an XML query tree over a probabilistic XML document, using the canonical tree edit distance as a similarity measure between subtrees. Probabilistic XML is a probability distribution model capturing uncertainty of both value and structure. Query over probabilistic XML documents is difficult: an naivie algorithm has exponential complexity by directly compute the tree edit distance between the query tree and each certain XML tree represented by the probabilistic XML document. Based on the method of tree edit distance computation over certain XML subtrees, we defined a minimum-solution to the edit distance computation, which means the minimum cost to translate the query tree to the probabilistic XML tree. Furthermore, we developed an algorithm---ASM (Algorithm of Subtree Matching) to compute the minimum solution. Finally, we proved the complexity of ASM is linear in the size of the probabilistic XML document.

• Periodical: Applied Mechanics and Materials (Volumes 571-572)
• Pages: 575-579
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.571-572.575
• Online since: June 2014
• Authors: Hai Tao Ma*, Chang Yong Yu, Chang Ming Xu, Miao Fang
• Keywords: Subtree Matching, Tree Edit Distance, Uncertain Data, XML Documents

References

[1] Andrew Nierman and H. Jagadish. Protdb: probabilistic data in XML. In Proceedings of the 28th international conference on Very Large Data Bases, 2002: pages 646-657.

DOI: 10.1016/b978-155860869-6/50063-9

[2] Benny Kimelfeld, Yuri Kosharovsky, and Yehoshua Sagiv. Query efficiency in probabilistic XML models. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, 2008, pages 701-714.

DOI: 10.1145/1376616.1376687

[3] Serge Abiteboul, Benny Kimelfeld, Yehoshua Sagiv, and Pierre Senellart. On the expressiveness of probabilistic XML models. The VLDB Journal, 2009, 18: 1041-1064.

DOI: 10.1007/s00778-009-0146-1

[4] Kuo-Chung Tai. The tree-to-tree correction problem. J. ACM, 1979, 26(3): 422-433.

[5] K. Zhang and D. Shasha. Simple fast algorithms for the editing distance between trees and related problems. SIAM J. Comput., 1989, 18(6): 1245-1262.

DOI: 10.1137/0218082

[6] Nikolaus Augsten, Denilson Barbosa, Michael Bohlen, and Themis Palpanas. Efficient top-k approximate subtree matching in small memory. IEEE Transactions on Knowledge and Data Engineering, 23(8): 1123-1137, (2011).

DOI: 10.1109/tkde.2010.245

[7] Ruiming Tang, Huayu Wu, Sadegh Nobari, and Stephane Bressan. Edit distance between XML and probabilistic XML documents. In Proceedings of the 22Nd International Conference on Database and Expert Systems Applications, DEXA'11, 2011, pages 448-456.

DOI: 10.1007/978-3-642-23088-2_33