3 ms·

Good experimental results! The high dimensionality (or non dimensionality) of the space can definitely hurt performance of spatial trees such as R-Trees, howeve

by timtadh 16y ago

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 in general the PQ-gram was so much faster the greater accuracy of ZSS didn't matter. [1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.149.7933 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.149.... [2] https://github.com/timtadh/zhang-shasha https://github.com/timtadh/zhang-shasha

jamii 16y ago
> ... if the variance is low ... Yes, thats a better way of putting it. The variance is so low that the tree always ended up very deep. I put a lot of effort into tuning bucket sizes etc but in the end it just didn't work out. > ... you could represent you formulae as trees instead of strings ... For some definitions of edit distance, the edit distance between two trees is equivalent to the Levenshtein distance between the in-order traversals of the trees. In any case, the tree structure of LaTeX itself tends to be quite flat and non-useful and the the tree structure of the equations themselves is hard to derive in general. ArXMLiv is working on this, among others, but its still a hard research problem. If I could get my hands on the tree structure I would be doing more sophisticated searches than edit distance, cf hoogle and uniquation.

by timtadh 16y ago

jamii 16y ago

> ... if the variance is low ... Yes, thats a better way of putting it. The variance is so low that the tree always ended up very deep. I put a lot of effort into tuning bucket sizes etc but in the end it just didn't work out. > ... you could represent you formulae as trees instead of strings ... For some definitions of edit distance, the edit distance between two trees is equivalent to the Levenshtein distance between the in-order traversals of the trees. In any case, the tree structure of LaTeX itself tends to be quite flat and non-useful and the the tree structure of the equations themselves is hard to derive in general. ArXMLiv is working on this, among others, but its still a hard research problem. If I could get my hands on the tree structure I would be doing more sophisticated searches than edit distance, cf hoogle and uniquation.