Persistent Data Structures
6.854 Notes #2

David Karger

1 Persistent Data Structures

Sarnak and Tarjan, "Planar Point Location using persistent trees", Communications of the ACM 29 (1986) 669–679

"Making Data Structures Persistent" by Driscoll, Sarnak, Sleator and Tarjan Journal of Computer and System Sciences 38(1) 1989

Idea: be able to query and/or modify past versions of data structure.

Goal: general technique that can be applied to any data structure.

2 Persistent Trees

Many data structures

Our goal: use simulation to transform any ephemeral data structure into a persistent one

Key principles:

Lazy approach:

Problem?

Full copy bad.

Fat nodes method:

Path copying:

Combined Solution (trees only):

Analysis idea: adversary has to do many changes to make copying expensive.

Analysis

3 Intro

remind about hash table survey

Talk about splay tree inserts and deletes

Make point about all at once

Remind about \(O(1)\) persistent pointer changes

4 Application: planar point location.

Persistent sorted sets:

5 Method: persistent red-black trees

Red black trees

Add persistence

Improvement:

Result: \(O(n)\) space, \(O(\log n)\) query time for planar point location.

Extensions: