Edit Distance between XML and Probabilistic XML Documents
| dc.contributor.author | TANG, Ruiming | en_US |
| dc.contributor.author | WU, Huayu | en_US |
| dc.contributor.author | NOBARI, Sadegh | en_US |
| dc.contributor.author | BRESSAN, Stephane | en_US |
| dc.date.accessioned | 2011-07-06T01:30:08Z | en_US |
| dc.date.accessioned | 2017-01-23T07:00:15Z | |
| dc.date.available | 2011-07-06T01:30:08Z | en_US |
| dc.date.available | 2017-01-23T07:00:15Z | |
| dc.date.issued | 2011-06-03 | en_US |
| dc.description.abstract | We propose an efficient algorithm for computing of the edit distance between an XML document and a probabilistic XML document. Probabilistic XML is a hierarchical data model capturing uncertainty of both value and structure. It is suitable to many modern applications such as information extraction, scientific data management and data integration. The computation of similarity is an essential building block for the comparison, alignment, clustering and classification of data in these applications. Several algorithms exist for measuring the structural similarity between XML documents among themselves or XML documents and XML document type definitions and schemas. The new challenge in efficiently computing the similarity between an XML document and a probabilistic XML document is the multiplicity of the possible worlds that a probabilistic XML document represents. In this paper, we devise and discuss algorithms for computing the similarity between an XML document and a probabilistic XML document. We empirically and comparatively evaluate their performance. In the absence of established corpora and benchmarks for probabilistic XML, we also propose and use random probabilistic XML models together with the associated random generation algorithms. | en_US |
| dc.format.extent | 366715 bytes | en_US |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/3472 | en_US |
| dc.language.iso | en | en_US |
| dc.relation.ispartofseries | TRB6/11 | en_US |
| dc.title | Edit Distance between XML and Probabilistic XML Documents | en_US |
| dc.type | Technical Report | en_US |