Stratified B-trees and versioned dictionaries.
Andy Twigg
Info
|
Date |
1st November 2011 (week , Michaelmas Term 2011) |
|
Time |
11:30 |
|
Place |
Abstract
We consider the problem of building a cache-oblivious dictionary supporting fast updates and versioning. For any
version $v$, let $N_{v}$ be the number of keys accessible (live) at $v$. Previously, the best known update bounds
for versioned dictionaries was $O(\log_B N_v)$, achieved by a number of structures. We present a new data structure,
the {\em Stratified Tree}, which supports updates in $O((\log N_{v})/B)$ amortized IOs and range queries of size $Z$ in
average case $O(\log N_{v} + Z/B)$ IOs. An implementation shows around 3 orders of magnitude improvement over copy-on-write
B-trees for updates. This can be seen as a fully-versioned analogue of the COLA of Bender et al. [SPAA2007]. An important
limitation is that we do not count IOs associated with operations on the version tree (for example, answering ancestorship
of two versions); it must fit into main memory. The remainder of the data structure is cache-oblivious, hence we call it
{\em semi-cache-oblivious}.
Further info
|
Related series |
|
