Persistence in Practice | Sune Keller
| | Abstract | The goal of the thesis is to theoretically analyse and compare Node Copying and Rollback, two approaches to making a data structure partially persistent (allowing the access of any previous version), and to evaluate in practice which of them is more suited for use in two di fferent usage scenarios: a sequential one, where operations are applied in long sequences generating versions with large data structures; and a randomized one, where operations are executed in a random order. A doubly linked list is used as the example data structure.
It is found that Node Copying performs signifi cantly better than Rollback in terms of space complexity regardless of the usage scenario. It also performs better in accessing a desired version in the randomized scenario independently of the data set size.
In the sequential scenario, when the data set is large enough, the smaller time complexity related to navigating the data structure at a given version makes an optimized implementation of Rollback faster than Node Copying at reaching a given index inside a desired version. | | Type | Master's thesis [Academic thesis] | | Year | 2012 | | Publisher | Technical University of Denmark, DTU Informatics, E-mail: reception@imm.dtu.dk | | Address | Asmussens Alle, Building 305, DK-2800 Kgs. Lyngby, Denmark | | Series | IMM-M.Sc.-2012-142 | | Note | | | Electronic version(s) | [pdf] | | Publication link | http://www.imm.dtu.dk/English.aspx | | BibTeX data | [bibtex] | | IMM Group(s) | Computer Science & Engineering |
|