next up previous
Next: References Up: Meaningful Change Detection in Previous: Related Work

Conclusion

   

We have described the need for computing semantically meaningful changes in structured data. We have introduced operations such as subtree copy and subtree move that allow us to describe changes to structured data more meaningfully than is possible by using only the traditional insert, delete, and update operations. We have formally defined the problem of computing a minimum-cost edit script, consisting of these operations, between two trees. To solve this problem, we have presented an algorithm that is based on representing an edit script between two trees as an edge cover of a bipartite graph induced by the trees. We have also studied the the performance of our algorithm both analytically and empirically. The experimental results, although preliminary, are very encouraging.



Sudarshan S. Chawathe
Sat Feb 22 12:28:02 PST 1997