Please use this identifier to cite or link to this item:
|Title:||A New Examination of Persistent Data Structures|
|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.|
|Type of Material:||Princeton University Senior Theses|
|Appears in Collections:||Computer Science, 1988-2017|
Files in This Item:
|PUTheses2015-Karp_Stefani.pdf||321.34 kB||Adobe PDF||Request a copy|
Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.