Partially persistent search trees with transcript operations

Abstract

When dictionaries are persistent, it is natural to introduce a transcript operation which reports the status changes for a given key over time. We discuss when and how a time and space efficient implementation of this operation can be provided.

Keywords

• complexity
• data structures
• search trees
• persistence
• complexity.
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]