Paper by Erik D. Demaine
- Erik D. Demaine, Pavel Panchekha, David Wilson, and Edward Z. Yang, “Blame Trees”, in Proceedings of the 13th Algorithms and Data Structures Symposium (WADS 2013), Lecture Notes in Computer Science, volume 8037, London, Ontario, Canada, August 12–14, 2013, pages 280–290.
We consider the problem of merging individual text documents, motivated by the
single-file merge algorithms of document-based version control systems.
Abstracting away the merging of conflicting edits to an external conflict
resolution function (possibly implemented by a human), we consider the
efficient identification of conflicting regions. We show how to implement
tree-based document representation to quickly answer a data structure inspired
by the “blame”' query of some version control systems. A “blame”' query
associates every line of a document with the revision in which it was last
edited. Our tree uses this idea to quickly identify conflicting edits. We show
how to perform a merge operation in time proportional to the sum of the
logarithms of the shared regions of the documents, plus the cost of conflict
resolution. Our data structure is functional and therefore confluently
persistent, allowing arbitrary version DAGs as in real version-control
systems. Our results rely on concurrent traversal of two trees with short
circuiting when shared subtrees are encountered.
- This paper is also available from SpringerLink.
- The paper is 10 pages.
- The paper is available in PDF (264k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated May 5, 2021 by