XIS: an XML document integration system

ABSTRACT

We describe XIS, an XML document integration system. The system is based on an algorithm that computes the top-down edit distance between an XML document and a schema. The complexity of the algorithm is t x s x log s, where t is the size of the document and s is the size of the schema.The system includes a GUI that allows the user to visualize the operations performed on the XML document. Synthesized and real data-sets will be used to show the efficiency and efficacy of the system.

REFERENCES

• 1: E. Rodney Canfield , Guangming Xing, Approximate XML document matching, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066857]
• 2: Nobutaka Suzuki, Finding an optimum edit script between an XML document and a DTD, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066825]
• 3: D. Shasha, K. Zhang, Approximate Tree Pattern Matching, Chapter 14 Pattern Matching Algorithms (eds. Apostolico, A. and Galil, Z.), Oxford University Press, June 1997.
• 4: M. Murata Hedge Automata: A Formal Model for XML Schemata http://www.xml.gr.jp/relax/hedge_nice.html

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.4 Hypertext/Hypermedia

General Terms:
Algorithms, Experimentation, Management

Keywords:
XML, document integration, tree grammar