ezyang's blog

the arc of software bends towards understanding

Blame Trees

August 12, 2013

I just presented Blame Trees at the 13th Algorithms and Data Structures Symposium. Blame trees are a functional data structure which support an efficient merge operation by incorporating information about the “blame” (think git blame) of any given part of the structure. It’s a theory paper, so the constant factors are not so good, but the asymptotics are much better than traditional merge algorithms used by modern VCSes.

This was joint work with David A. Wilson, Pavel Panchekha and Erik D. Demaine. You can view the paper or check out the slides. I also have a slightly older version of the talk recorded on YouTube (20 minutes) which I had used to help get feedback from my out-of-town collaborators before actually giving the talk. Thanks also to David Mazières for giving useful comments on the presentation in person.

3 Comments

  1. K. J.
    Interesting reading. I also found another recent paper on three way merges with similar performance: They use treaps instead of rb-trees to get history independent balancing. http://arxiv.org/abs/1301.3388
  2. Edward Z. Yang
    Nice find! I’ll have to take a look.
  3. S.N.M
    It is fantastic I understand lot of things about Blame