User:Francis Tyers/MT

Schubert, E., Schaffert, S., and Bry, F. (2005). "Structure-preserving difference search for xml documents". Proceedings of the Extreme Markup Languages 2005 Conference, 1-5 August 2005, Montréal, Quebec, Canada

Structure-Preserving Difference Search for XML Documents

The paper presents a strategy for measuring the difference between a pair of documents in XML. The authors report that this is an improvement over the more traditional strategies. The two traditional strategies tested against were longest common subsequence (LCS), as used by GNU diff -- which operates on the level of lines in a file, and shortest edit distance, as used by XMLDiff and similar programs -- which operates on nodes in a document tree. The authors state that the deficiency in these methods lies in the way that they do not represent changes as made by authors. Rather they try to make the "smallest possible" edit script or diff.

The authors present their method of "structure preserving difference", which instead of trying to find the smallest possible edit script, attempts to maximise the size of retained sub-structures maintained in changing one document to another. In order to calculate this, they model the document as a graph, where relations other than simple parent-child can be taken into account, for example ancestor-descendent, and sibling relationships.

Retained sub-structures are calculated as nodeset correspondences (set of mappings between equal nodes) between the original, and modified document. Two nodes are considered equal when they match a node similarity relation, which is user-specified. The most simple node similarity relation would be to consider two nodes equal when the labels are equal. Between two documents, there are many nodeset correspondences, so an algorithm needs to be used to find the optimal set of correspondences which maximises the retained sub-structures.

The algorithm used is Dijkstra's algorithm, where the edge weights are calculated by different cost functions. The authors outline four possible cost functions.

Review

Revision 1 
"Structure-preserving difference search for XML documents"

Reviewer Recommendation Term: 
Revisions
Comments to Editor: 
Review Sheet: General Judgement
============================================================

1. Is the paper acceptable for publication

(a)   in its present form?    NO
(b)   with minor revisions?   YES

Should the paper be reconsidered after major revision? 

Is it unacceptable for publication?

2. Please list any other general comments or specific suggestions in the separate blind comments to author's box.

Comments to Author: 

There are numerous minor errors in the English, some of which will be outlined below. The paper
would benefit from a thorough proof-reading.

Comments on Paper:

The introduction clearly lays out the problem. The state of the art section is fairly well written, with a couple of 
minor quibbles that should be taken care of. The explanation of the methodology is adequate. 



Regarding formatting, the style is less than optimal, equations are typeset too small, code fragments overlap the
margins of the page, the text is not justified, simple dashes are used where mdashes should be used. Sometimes 
figures span over pages, which makes them hard to read.

A list follows:

* p.1  ... from _text oriented documents over languages aimed at exchanging messages between peers_ to ...
 
           What the underlined section means is not clear. Perhaps a "from X to Y and Z" would be a better
           structure for this section.

* p.1  ... is so-called difference search ...
 
           is so-called → is the so-called

* p.1  ... must both be ... and be ...

           → must be both ... and ...

* p.2  The idea of "user-defined relations" could use some more explanation.

* p.2  ... allows to add extensions easily.

           → allows extensions to be easily added.

* p.2  It is stated that "three different cost functions" will be suggested, when in fact, there are four.

* p.2  The output described is not the default output of the diff program, which uses less-than and greater-than
       symbol, but rather the 'unified diff', -u, output. 

* p.3  In giving the deficiencies of 'diff', it is stated that whitespace is significant. This is not entirely 
       correct, the -w and -b options give the option of ignoring white space, although as the authors point out extra
       blank lines are still significant. This should be clarified. 

* p.3  It isn't clear in Figure 3 how the tags are mismatched. 

* p.4  An example of _this kind of systems_ ...

       → these kinds of systems ...

* p.4  ... that allows to include ...

       → that allows the inclusion of ...

* p.5  What the "solution" may be is not defined and not immediately obvious. 

* p.5  ... actual difference _are_ obviously ...

       → is

* p.6  Having (document graph of the) in parentheses twice in the same sentence is a bit difficult to read,
       this could benefit from being re-worded.

* p.6  ... we _shall usually_ ...

       → will [typically]

* p.6  ... also allows _to model_ ...

       → "us to model" or "the modelling of" 

* p.7  The <em> and <i> tags are not as far as I know semantically equal. They belong to different groups of
       of tags in XHTML (text and presentational respectively), and the semantics will vary depending on 
       style-sheet. Emphasising (<em>) something could mean putting it in bold face, it does not necessarily
       mean italicising it.

* p.7  ... the node similarity relation can in most cases not be derived ...  

       → ... in most cases, the node similarity relation cannot be derived ...
       → ... the node similarity relation can in most cases neither be derived from the data, nor ...

* p.7  Re-write the part in parentheses, "To a certain degree, X could be an interesting solution"

* p.7  Complexity of the task ...
   
       → The complexity of the task ...

* p.7  If every of these nodes is similar to every node in ...
      
       Re-write this sentence, the confusion between "every", "all" and "each" makes it difficult to 
       understand. Check verb agreement "nodes is" → "nodes are".

* p.8  Comments about Dijkstra's algorithm, e.g. named, described, taught etc. are probably superfluous.

* p.10 The sentence starting "Informally..." is too long, split it into two, probably around the "and".

* p.10 Move the part in parentheses starting "other node ..." to a footnote, as it disrupts the flow of
       the sentence. 


* p.11 ... credits value ...

       → credit value ...

* p.12 It would be nice with the first example to display the output of GNU diff for comparison. 
      
       ---- 

       $ diff -uw /tmp/1~ /tmp/2~
       --- /tmp/1~      2008-04-05 20:30:14.000000000 +0100
       +++ /tmp/2~      2008-04-05 20:30:10.000000000 +0100
       @@ -11,10 +11,10 @@
            <title2>
              and the Order of the Phoenix
             </title2>
       -    <edition>Hardcover</edition>
       +    <edition>Paperback</edition>
            <author>J. K. Rowling</author>
       -    <price>19.79</price>
       -    <isbn>043935806X</isbn>
       +    <price>8.49</price>
       +    <isbn>0439358078</isbn>
          </book>
          <book>
            <rank>2</rank>
       @@ -24,9 +24,9 @@
            <title2>
              and the Order of the Phoenix
            </title2>
       -    <edition>Paperback</edition>
       +    <edition>Hardcover</edition>
            <author>J. K. Rowling</author>
       -    <price>8.99</price>
       -    <isbn>0439358078</isbn>
       +    <price>17.99</price>
       +    <isbn>043935806X</isbn>
          </book>
        </charts>

       ----