The Dense Skip Tree: A Cache-Conscious Randomized Data Structure

Report
Authors:Spiegel, Michael, Department of Computer ScienceUniversity of Virginia Reynolds, Paul, Department of Computer ScienceUniversity of Virginia
Abstract:

We introduce the dense skip tree, a novel cache-conscious randomized data structure. Algo- rithms for search, insertion, and deletion are presented, and they are shown to have expected cost O(log n). The dense skip tree obeys the same asymptotic properties as the skip list and the skip tree. A series of properties on the dense skip tree is proven, in order to show the probabilistic organization of data in a cache-conscious design. Performance benchmarks show the dense skip tree to outperform the skip list and the self-balancing binary search tree when the working set cannot be contained in cache.

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Spiegel, Michael, and Paul Reynolds. "The Dense Skip Tree: A Cache-Conscious Randomized Data Structure." University of Virginia Dept. of Computer Science Tech Report (2009).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
2009