• 6.5210/18.415: Advanced Algorithms
  • PSets
  • Calendar
  • Materials
  • Information
  • Persistent Data Structures

    David Karger

    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.

    Persistent Trees

    Many data structures

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

    Key principles:

    Lazy approach:


    Full copy bad.

    Fat nodes method:

    Path copying:

    Combined Solution (trees only):

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


    Application: planar point location.

    Persistent sorted sets:

    Method: persistent red-black trees

    Red black trees

    Add persistence


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