Optimal query/update tradeoffs in versioned dictionaries

Details Optimal query/update tradeoffs in versioned dictionaries Optimal query/update tradeoffs in versioned dictionaries

2011-03-13

arxiv.org/abs/1103.2566v2

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Optimal query/update tradeoffs in versioned dictionaries does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal query/update tradeoffs in versioned dictionaries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal query/update tradeoffs in versioned dictionaries will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-258801