Skip navigation
Please use this identifier to cite or link to this item:
Title: Zip Trees: A New Approach to Concurrent Binary Search Trees
Authors: Timmel, Stephen
Advisors: Tarjan, Robert E.
Contributors: Chudnovsky, Maria
Department: Mathematics
Certificate Program: Applications of Computing Program
Class Year: 2017
Abstract: One of the most fundamental tasks in computing is the storage and retrieval of data. For this reason, binary search trees are one of the most fundamental algorithms in computer science. In the last few years, the ever-present need for data access has been accompanied by a need for multiple processors to access data concurrently. Concurrent programming is a deeply theoretical field of study focused on developing algorithms and techniques for managing this increased interest in parallel processing. Binary search trees typically present three main difficulties in a concurrent environment: their reliance on global information and balance, their use of read and write operations which traverse the tree in different directions, and the amplified cost of changing pointers near the root (where many threads must traverese). We develop a new algorithm known as a Zip Tree which overcomes all three challenges by maintaining balance based solely on locally stored random values, updating the tree structure from the top down, and inserting at a height constant in expectation within the tree.
Type of Material: Princeton University Senior Theses
Language: en_US
Appears in Collections:Mathematics, 1934-2020

Files in This Item:
File SizeFormat 
thesis_1.pdf493.5 kBAdobe PDF    Request a copy

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