Item Details

Print View

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

Spiegel, Michael; Reynolds, Paul
Format
Report
Author
Spiegel, Michael
Reynolds, Paul
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.
Language
English
Date Received
2012-10-29
Published
University of Virginia, Department of Computer Science, 2009
Published Date
2009
Collection
Libra Open Repository
In CopyrightIn Copyright
▾See more
▴See less

Availability

Access Online