Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Idea to Innovation

University of Alberta

$10,000.00

VTracker: domain-independent and domain-aware XML-document differencing

EF 2012-13

Résumé
XML, the Extensible Markup Language, is the standard exchange format for modern Information Systems, Service Oriented Architecture (SOA) and the Semantic Web. Hence, comparing XML documents has become a necessary task for tracking and merging changes between versions of the same document, or for translating between documents referring to the same information but complying with different schemata or originating from different parties. In this scenario, given two documents, XML differencing is the process of finding an edit sequence, namely a sequence of exact and approximate matching, deletion, and insertion operations, which, if applied to the first document will result in the second. In practice, domain-specific differencing solutions are expensive to develop, and hard to reuse. Therefore, a generic differencing approach, able to serve various domains, would be both useful and cost-effective. VTracker is a generic XML differencing approach, which is capable of capturing domain knowledge and semantics through a configurable domain-specific cost function. VTracker views an XML document as an ordered labeled tree. Given two XML-document trees and a cost function VTracker calculates the tree-edit distance needed to transform one tree to the other. The first contribution of VTracker is an automatic method used to synthesize such a cost function based on the domain's XML Schema Definition (XSD). Second, VTracker considers the XML reference structure in addition to the natural XML containment structure. Third, VTracker implements an affine-cost policy that prefers edit operations applied to neighbors over dispersed elements. Finally, VTracker uses a set of simplicity heuristics to nominate the best edit script in case of multiple ones found with the same minimum cost. VTracker has been applied to a variety of domains, namely OWL/RDF, WSDL, BPEL, UML/XMI, XHTML, and RNA secondary structure, where it performed competitively with, or even better than, state-of-the- art methods in each of these domains.
Programme
Idea to Innovation
Bénéficiaire
Emplacement
Alberta, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
430464-2012
Name nom
Stroulia, Eleni
Department département
Computing Science
Organization id
9
Institution établissement
University of Alberta
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2012
Award amount
10000
Program id
I2IPJ
Program name en
Idea to Innovation
Program name fr
De l'idée à l'innovation
Group en
Research partnerships programs
Group fr
Programmes de partenariat
Committee code
96
Committee name en
RPP Internal Decision Cttee
Committee name fr
Cté de décision interne - PPR
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Partie
1
Nb partie
1
Application title
VTracker: domain-independent and domain-aware XML-document differencing
Keyword
NSERC
Application summary
XML, the Extensible Markup Language, is the standard exchange format for modern Information Systems, Service Oriented Architecture (SOA) and the Semantic Web. Hence, comparing XML documents has become a necessary task for tracking and merging changes between versions of the same document, or for translating between documents referring to the same information but complying with different schemata or originating from different parties. In this scenario, given two documents, XML differencing is the process of finding an edit sequence, namely a sequence of exact and approximate matching, deletion, and insertion operations, which, if applied to the first document will result in the second. In practice, domain-specific differencing solutions are expensive to develop, and hard to reuse. Therefore, a generic differencing approach, able to serve various domains, would be both useful and cost-effective. VTracker is a generic XML differencing approach, which is capable of capturing domain knowledge and semantics through a configurable domain-specific cost function. VTracker views an XML document as an ordered labeled tree. Given two XML-document trees and a cost function VTracker calculates the tree-edit distance needed to transform one tree to the other. The first contribution of VTracker is an automatic method used to synthesize such a cost function based on the domain's XML Schema Definition (XSD). Second, VTracker considers the XML reference structure in addition to the natural XML containment structure. Third, VTracker implements an affine-cost policy that prefers edit operations applied to neighbors over dispersed elements. Finally, VTracker uses a set of simplicity heuristics to nominate the best edit script in case of multiple ones found with the same minimum cost. VTracker has been applied to a variety of domains, namely OWL/RDF, WSDL, BPEL, UML/XMI, XHTML, and RNA secondary structure, where it performed competitively with, or even better than, state-of-the- art methods in each of these domains.