Skip navigation
Please use this identifier to cite or link to this item:
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
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    Request a copy

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