Persistent Data Structures (Version Control) Ephemeral v0 Partial persistence version list Full persistence version tree v0 Confluently persistence version DAG v0 Purely functional v0 car cdr update v1 v1 v2 v3 v3 v4 v4 v5 v5 v2 v3 v6 v4 v5 query v6 update & query v3 v5 updates at leaves any version can be copied query all versions update/merge/query all versions Retroactive v0 v6 v1 v2 query onlyy v2 v1 never modify only create new pairs only DAGs v1 v2 v3 update & query all versions updates in the past propragate v4 1 Planar Point Location T1 T2 T3 T4 T5 T6 update O(n∙log n) preprocessing, O(log n) query T7 Partial persistent search trees 2 Path copying (trees) root pointer c a c f d f g e 3 Partial persistence ƒ Version ID = time = 0,1,2,... 012 ƒ Fast node ((anyy data structure)) field1: (0,x) (3,y) (7,z) – record all updates in node field2: (0,a) (14,c) (16,b) (version,value) pairs – field updates O(1) – field fi ld queries i ≡ predecessor d wrt version i id ((search h tree/vEB) / ) ƒ Node copying (O(1) degree data structures) –P Persistent i t t node d = collection ll ti off nodes, d each h valid lid ffor an interval of versions, with Δ extra updates, Δ = max indegree – pointers must have subinterval of the node pointing to; otherwise copy and insert pointers (cacading copying) NB: Needs to keep track of back‐pointers [0,8[ field1: field2: (0,x) (3,y) [8,13[ field1: (8,z) (10,w) [13,∞[ field1: (13,w) (q5,y) (0,a) (7,c) field2: field2: (8,c) (9,d) (13,e) (14,c) 4 Full persistence 1 4 increasing version 7 3 5 2 1 preorder d traversall 6 4 7 5 3 6 2 Version i lilist (order maintenance data structure) Version tree (numbers = version ids) ƒ Fat node field: ((1,x) , ) ((7,z) , ) ((5,x) , ) ((6,y) ,y) ((2,x) , ) – Updates p ((1,x) , ) ((6,y) ,y) ((7,z) , ) to a field – Queries = binary search among versions – Update (7,z): Insert 7 as leftmost child of 4; insert pairs for 7 and 5=succ(7) ƒ Node splitting (≥2Δ ekstra fields) [[0,∞[ , [ [4,3[ field1: (1,a) (4,b) (3,a) (2,c) field2: (1,f) (7,g) (5,f) [[0,5[[ [5,3[ [4,5[ [[5,∞[[ split field1: (1,a) (4,b) field1: (5,b) (3,a) (2,c) version 5 field2: (1,f) (7,g) field2: (5,f) 5 Persistence techniques [N. Sarnak, R.E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, 29(7), 669‐679, 1986] ƒ Partial p persistence,, trees,, O(1) ( ) access,, amortized O(1) ( ) update p [J.R. Driscoll, N. Sarnak, D.D. Sleator, R.E. Tarjan, Making Data Structures Persistent, Journal of Computer and System Sciences, 38(1), 86‐124, 1989] ƒ P Partial i l & full f ll persistence, i O(1) degree d d data structures, O(1) access, amortized O(1) update [P.F. Dietz, R. Raman, Persistence, Amortization and Randomization. Proceedings 2nd Annual ACM ACM‐SIAM SIAM Symposium on Discrete Algorithms, Algorithms 78‐88, 78 88 1991] [G.S. Brodal, Partially Persistent Data Structures of Bounded Degree with Constant Update Time, Nordic Journal of Computing, volume 3(3), pages 238‐255, 1996] ƒ Partial persistence, O(1) degree data structures, O(1) access & updates update [P.F. Dietz, Fully Persistent Arrays. Proceedings 1st Workshop on Algorithms and Data Structures, LNCS 382, 67‐74, 1989] ƒ Full persistence, RAM structures, O(loglog n) access, O(loglog n) amortized expected updates 6 Comparison of persistence techniques ƒ Copy data structure for each version – no query overhead, slow updates & wastes a lot of space ƒ Record updates & keep current version – fast updates & queries to current version, space efficient, slow queries in the past ƒ Path copying – applies to trees, no query overhead, space overhead = depth of update ƒ Fat node – partial persistence: O(1) updates and space optimal, loglog n query overhead – full persistence: O(loglog n) expected amortized updates and space optimal, loglog n query overhead ƒ Node copying/splitting – fast updates & queries (amortized updates for full persistence) – onlyy works for p pointer‐based structures with O(1) ( ) degree g 7