2011/03/13 by Andrew Byde, Andy Twigg, Byde, Andrew +1
Computer Science · #Advanced Database Systems and Queries #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #Distributed systems and fault tolerance #FOS: Computer and information sciences #cs.DB #cs.DS
paper · pdf · doi:10.48550/arxiv.1103.2566
openalex publication_date 2011/03/13 · arxiv created 2011/04/12 · arxiv updated 2015/03/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.