arXiv:1103.2566cs.DS
Optimal query/update tradeoffs in versioned dictionaries
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
Abstract
External-memory dictionaries are a fundamental data structure in file systems and databases. Versioned (or fully-persistent) dictionaries have an associated version tree where queries can be performed at any version, updates can be performed on leaf versions, and any version can be `cloned' by adding a child. Various query/update tradeoffs are known for unversioned dictionaries, many of them with matching upper and lower bounds. No fully-versioned external-memory dictionaries are known with optimal space/query/update tradeoffs. In particular, no versioned constructions are known that offer updates in $o(1)$ I/Os using O(N) space. We present the first cache-oblivious and cache-aware constructions that achieve a wide range of optimal points on this tradeoff.
If we're replacing blog links with arXiv abstract links, note that there are actually two papers linked, both interesting. "Stratified B-trees and versioning dictionaries" http://arxiv.org/abs/1103.4282 This is actually the newer paper, and presents the "Stratified B-Tree" data…
jholmanView on HNParent context