zhang-shasha

A good general method for comparing ASTs is Tree Edit Distance. I have an implementation in python https://github.com/timtadh/zhang-shasha . If computing the exact distance is too slow you can use an approximate algorithm https://github.com/timtadh/pygram .

The list diff is really a set diff, if I understand it right, in that it disregards order and multiple instances? That should only happen if the dict member is a set. Members which are lists should be treated using a Levenshtein-distance style patch. For free you then get patching of string members. I'm getting ambitious now, but what about tree-edit distance (with patch script) for members which are nested lists? There is Python code out there for these: https://github.com/timtadh/zhang-shasha https://code.google.com/p/py-editdist EDIT I have only used the above libraries for distances, not for patchable diffs. But the Levenshtein and tree-edit distance algorithms are amenable to outputting the patch scripts.

Good experimental results! The high dimensionality (or non dimensionality) of the space can definitely hurt performance of spatial trees such as R-Trees, however for distance trees what really kills you is the the metric to compute the distance. There can be a couple of problems with it: 1) if it takes a long time to compute that will obviously hurt you, 2) if the variance is low or if some distances are meaningless the tree will be mishapped. I was thinking as I was going over the article again that you could represent you formulae as trees instead of strings. This might yield more accurate/interesting distances. I recently used the PQ-gram distance[1] to compare subsets of ASTs with great success. PQ-gram is a really fast approximation of tree edit distance. I also tried using exact edit distance with the Zhang-Shasha algorithm[2], but