Date Added: Jan 2010
The success of XML has recently renewed interest in change control on trees and semi-structured data. This is motivated, for instance, by the need to manage versions of documents, to query and monitor changes and to efficiently exchange documents and their updates. In many applications, the changes that occurred between two versions of a document are unknown to the system. Hence, a diff algorithm is used to construct a delta representing the changes. Various diff algorithms have been proposed. Some run in quadratic time and space cost while others run in linear time. Some consider the tree structure of XML documents while others do not. Also, some algorithms may find a more "Concise" sequence of changes.