2009.02.26 | Gerth Stølting Brodal

Abstract
In this thesis we are presenting different techniques for analysing algorithms
designed for skew access sequences along with properties, which categorises these
algorithms. Furthermore are we describing some related data structures, which
support the working set, queueish, emphdynamic finger and the unified property.
We also describe how to implement data structures which supportsthese properties
in practice.
One of the main results inthis thesis is the description and implementation of the
dynamic self adjusting skip lists, which is developed by Prosenjit Bose, Karim
Douïeb and Stefan Langerman from their 2008 paper “Dynamic optimality for skip
lists and B-trees”. The implementation is accompanied with a detaileddescription
of the data structure and its common operations search, insert, and delete. This
implementation is tested against an implementation of splay trees developed
byDaniel Slaetor and Robert E. Tarjan and presented in the paper from 1985
“Self-adjusting binary search trees”. The splay trees are a commonly used
data structure for skewaccess sequences due to its easy implementation. The
disadvantage of this data structure is its potential bad I/O and cache performance.
Minimising cache faults and keeping locality is difficult in this structure. The
dynamic self adjusting skip lists has some advantages in preserving locality, as we
will see in this thesis, but the structure ishard to implement and has a constant
factor hidden in theBig-O notation. The results are therefore not surprisinglythat
dynamic self adjusting skip lists are performing worse than splay trees even though
they are better at preserving locality. The results of the empirical tests in this thesis
are therefore not surprising that splay trees performs equally good or better under
the different tested scenarios.
To compensate for the growing number of elements in data collections we are in
this thesis also presenting P. Bose et al. dynamic I/O effective B-trees, which they
contribute in the same paper, to solve the adaptive dictionaryproblem in external
memory. They have used Brian C. Dean and Zachary H. Jones’ translation scheme
from 2007 to translate dynamic self adjusting skip lists to dynamic I/O efficient
B-trees. We are in details describing the translation scheme and the resulting
dynamic I/O effecient B-treesdata structure.
February 28, 2009