Article

Computing edit distances between an XML document and a schema and its application in document classification

Authors:

Guangming Xing,

Chaitanya R. Malla,

Snigdha Dantala VenkataAuthors Info & Claims

SAC '06: Proceedings of the 2006 ACM symposium on Applied computing

Pages 831 - 835

https://doi.org/10.1145/1141277.1141467

Published: 23 April 2006 Publication History

Abstract

In this paper, we present an algorithm to find a sequence of top-down edit operations with minimum cost that transforms an XML document such that it conforms to a schema. It is shown that the algorithm runs in O(p x log p x n), where p is the size of the schema(grammar) and n is the size of the XML document (tree). We have also shown that edit distance with restricted top-down edit operations can be computed the same way.We will also show how to use the edit distances in document classification. Experimental studies have shown that our methods are effective in structure-oriented classification for both real and synthesized data sets.

References

[1]

Nobutaka Suzuki, Finding an Optimum Edit Script between an XML Document and a DTD, Proceedings of ACM Symposium on Applied Computing, pp. 647 - 653, March, 2005, Santa Fe, NM.

Digital Library

[2]

Rodney Canfield, Guangming Xing, Approximate XML Document Matching (Poster), Proceedings of ACM Symposium on Applied Computing, March, 2005, Santa Fe, NM.

Digital Library

[3]

T. Bray, J. Paoli, M. Sperberg-McQueen, and etl., Extensible Markup Language (XML) 1.0 (Third Edition), W3C, http://www.w3.org/TR/2004/REC-xml-20040204/.

[4]

D. Shasha, K. Zhang, Approximate Tree Pattern Matching, Chapter 14 Pattern Matching Algorithms (eds. Apostolico, A. and Galil, Z.), Oxford University Press, June 1997.

[5]

E. Tanaka, K. Tanaka, The Tree-to-tree Editing Problem, International Journal of Pattern Recognition and Artificial Intelligence, 2, (2), pp.221--240, 1988.

[6]

M. Murata Hedge Automata: A Formal Model for XML Schemata http://www.xml.gr.jp/relax/hedge_nice.html

[7]

G. Myers Approximately Matching Context Free Languages, Information Processing Letters, 54, 2, pp. 85--92, 1995.

Digital Library

[8]

E. Bertino, G. Guerrini, M. Mesiti, A Matching algorithm for measuring the structural similarity between an XML document and a DTD and its applications, Info. Systems, V29, pp 23--46, 2004.

Digital Library

[9]

A. Boukottaya, C. Vanoirbeek, F. Paganelli, O. Abou Khaled, Automating XML Documents Transformations: A Conceptual Modelling Based Approach, Proceedings of 1st Asian-Pacific conference on Conceptual modelling, Dunedin, NZ, pp81 - 90 2004.

Digital Library

[10]

D. Reis, P. Golgher, A. Silva, A. Laender, Automatic web news extraction using tree edit distance, WWW'04, 2004, pp 502--511, Manhattan, NY, 2004.

Digital Library

[11]

W. Chen, New Algorithm for Ordered Tree-to-Tree Correction Problem, J. of Algorithms, 40:135--158, 2001.

Digital Library

[12]

A. Nierman, H. V. Jagadish, Evaluating structural similarity in XML documents, WebDB 2002, Madison, Wisconsin, June 2002.

[13]

XML Document Mining Challenge, http://xmlmining.lip6.fr/

[14]

B. Chidlovskii, Schema Extraction from XML Data: A Grammatical Inference Approach, KRDB'01 Workshop, Rome, Italy, September 15, 2001.

[15]

WEKA Project, http://www.cs.waikato.ac.nz/ml/weka/

Cited By

Han YKo S(2019)Alignment Distance of Regular Tree LanguagesTheoretical Computer Science10.1016/j.tcs.2019.06.022Online publication date: Jul-2019
https://doi.org/10.1016/j.tcs.2019.06.022
Tekli JChbeir RTraina ATraina CFileto R(2015)Approximate XML structure validation based on document-grammar tree similarityInformation Sciences: an International Journal10.1016/j.ins.2014.09.044295:C(258-302)Online publication date: 20-Feb-2015
https://dl.acm.org/doi/10.1016/j.ins.2014.09.044
Horie KSuzuki NShin SMaldonado J(2013)Extracting differences between regular tree grammarsProceedings of the 28th Annual ACM Symposium on Applied Computing10.1145/2480362.2480527(859-864)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.1145/2480362.2480527
Show More Cited By

Index Terms

Computing edit distances between an XML document and a schema and its application in document classification
1. Information systems
  1. Information retrieval
  2. Information storage systems
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Approximate XML structure validation based on document-grammar tree similarity

Comparing XML documents with XML grammars, also known as XML document and grammar validation, is useful in various applications such as: XML document classification, document transformation, grammar evolution, XML retrieval, and the selective ...
Finding an optimum edit script between an XML document and a DTD
SAC '05: Proceedings of the 2005 ACM symposium on Applied computing

Finding an optimum edit script between data plays an important role in data retrieval and data transformation. Many methods for finding an optimum edit script between two XML documents have been proposed so far, but few studies on finding an optimum ...
XML-based XML schema access
WWW '07: Proceedings of the 16th international conference on World Wide Web

XML Schema's abstract data model consists of components, which are the structures that eventually define a schema as a whole. XML Schema's XML syntax, on the other hand, is not a direct representation of the schema components, and it proves to be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '06: Proceedings of the 2006 ACM symposium on Applied computing

April 2006

1967 pages

ISBN:1595931082

DOI:10.1145/1141277

Conference Chair:
Hisham M. Haddad
Kennesaw State University, Kennesaw, Georgia

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 April 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SAC06

Sponsor:

SIGAPP

SAC06: The 2006 ACM Symposium on Applied Computing

April 23 - 27, 2006

Dijon, France

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
276
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Han YKo S(2019)Alignment Distance of Regular Tree LanguagesTheoretical Computer Science10.1016/j.tcs.2019.06.022Online publication date: Jul-2019
https://doi.org/10.1016/j.tcs.2019.06.022
Tekli JChbeir RTraina ATraina CFileto R(2015)Approximate XML structure validation based on document-grammar tree similarityInformation Sciences: an International Journal10.1016/j.ins.2014.09.044295:C(258-302)Online publication date: 20-Feb-2015
https://dl.acm.org/doi/10.1016/j.ins.2014.09.044
Horie KSuzuki NShin SMaldonado J(2013)Extracting differences between regular tree grammarsProceedings of the 28th Annual ACM Symposium on Applied Computing10.1145/2480362.2480527(859-864)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.1145/2480362.2480527
Banner RBarkol OBergman RGolan SCarmel YIsh-Hurwitz IZilinsky O(2011)Automatic Policy Rule Extraction for Configuration ManagementProceedings of the 2011 IEEE International Symposium on Policies for Distributed Systems and Networks10.1109/POLICY.2011.13(125-128)Online publication date: 6-Jun-2011
https://dl.acm.org/doi/10.1109/POLICY.2011.13

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents