Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01dr26z071p
 Title: A New Examination of Persistent Data Structures Authors: Karp, Stefani Advisors: Tarjan, Robert Department: Computer Science Class Year: 2015 Abstract: This thesis revisits algorithms for making pointer-based data structures persistent, specifically the node-copying and node-splitting algorithms developed in the late 1980s. A primary source of complexity in these algorithms is the necessity of maintaining inverse pointers from each node to its predecessors in the persistent data structure. One of the main focuses of this thesis is the role of these inverse pointers, with the ultimate goal of eliminating them from the data structure without affecting the amortized space and time bounds. Ultimately, we present a new, lazier algorithm derived from the original node-splitting algorithm which eliminates inverse pointers and runs in comparable space and time. We also present a simplified algorithm for the special case of making binary trees partially persistent, which takes advantage of the special structure of trees and partial persistence to eliminate amortization from the analysis and instead produce worst-case bounds. Extent: 44 pages URI: http://arks.princeton.edu/ark:/88435/dsp01dr26z071p Type of Material: Princeton University Senior Theses Language: en_US Appears in Collections: Computer Science, 1988-2016

Files in This Item:
File SizeFormat
PUTheses2015-Karp_Stefani.pdf321.34 kBAdobe PDF

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.