Video 4-6: Partial Persistence Analysis

0:02 And we're trying to implement this general transformation. If you're given an ephemeral data structures or standard normal data structure with a few uh terms and conditions, namely it has to be a linked data structure. Let me go back to this picture here that I tried to draw. Linked data structure essentially means it consists of fixedsiz nodes. Even here is forced to be of a single type. This is without loss of generality though. Uh so they have a a constant bounded number of different fields which can hold any values like numbers or pointers to other nodes and on top of that the only thing we have is a constant number or bounded number of access pointers or the the handles from the outside where we can get started. Think of the root of a binary search tree or head and tail of a linked list. That's a linked data structure. uh we need this one additional condition for the whole construction to work which is bounded inderee in a graph theory sense every node is the target of of a bounded number of pointers from other nodes and that turns out to be crucial again this is it is a restriction there's data structures that don't satisfy this um I was about to say Fibonacci heaps but that's not true It's Fibonacci heaps don't satisfy this but there's a different reason you can think about why there are not a bounded inderee linked data structure. You can try to get rid of the obstacle but it turns out that's only known to be possible by having unbounded inderee then so for for now we don't know whether we can make Fibonacci heaps persistent with this technique.

1:43 uh I'll I'll come back to other data structure questions where this theorem does not apply but for now let's let's assume it does. So our ephemeral data structure is a linked data structure bounded in degree then we can make it partially persistent as at essentially no extra cost apart from constant factors uh both in terms of space for every update step. Remember these crucial distinctions. Operation was the high level operation on the data structure and update step is a single atomic right to one of the fields in in the nodes. So we have um constant extra space for each of these update steps. It's kind of necessary because we need to keep the past and we have a constant factor slowdown for operations but not more than that. um all the previous tricks that we've seen including copy on right and these fat nodes they couldn't do uh all of this but it turns out going somewhere in between of these two extremes does work what do we need to do for that first of all for every ephemeral node x we'll denote by this xbar the persistent version of that note maybe is good to mention here as And we need those to be a little bit bigger. Uh we essentially need these E + one additional fields. And they're um the one is just a single pointer, but the E extra fields are update boxes that can hold this triple of a version timestamp, the name of the field that we changed, and the new value that we write, which could be um which can only be a pointer really. Uh we only do this for pointers as you'll see the number of these extra pointers you can set to essentially p which was the in degree uh yeah stated here you can use a few more there's a trade-off between time and space in the end okay uh we've already figured out how to do accesses basically not much changes except that whenever you access a field in a node you have to go through the update boxes and see if there's been a change. From what I just said, you only really have to do this for pointers, but uh it's a constant overhead because the number of update boxes is is constant.

4:11 Then um we'll go through in detail what we do in an update step. Uh when think of always trying to do it locally without escalating changes, which means use an update box if there's a free one. then you just put the current time stamp and the field you're changing in the new value and then you're done. Um only if you run out of update boxes things get more complicated. And what what happens is that you may form um a chain of copies of the same ephemeral node X where this is a a linked list with this extra pointer to keep be able to um to trace through those if needed. But there's all always going to be just one life persistent copy of such a an X. All the others are dead which means they don't receive updates anymore but they need to be kept so that we can still access past oper past versions.

5:03 Okay. um crucial invariant for the access operations is that whenever some node points to another node in a specific version in the ephemeral data structure then we do have such an entry in the persistent version. That's basically all all it says in concrete words is that we don't mess up things with our updates and copies and these things. So that indeed accesses can stay local. If you reach a certain persistent note, you're going to find an entry for the appropriate field in that version. If you reached it following the entry um the access pointer for the right version, you're going to reach a persistent copy that has again an entry for the right version.

5:52 How do we do updates to make sure that this invariant um is is satisfied throughout time? I already said um we do individual update steps which may be interspersed with further accesses. Um but then an individual update step can essentially be one of uh three things that's given by the model. Uh one option is we allocate a new node And well if we do that we allocate a new persistent node.

6:44 What I should have said is uh this is the update step that the ephemeral data structure would have done in our persistent version. We instead allocate the slightly larger persistent note and we also give it a time stamp of the current version.

7:08 Uh I have the version anywhere already. Let's just call it V again. So V is the current current time. We're now doing this update. Um and other than that, not much uh has to happen. I'm not sure I mentioned timestamps for nodes before, right? uh whenever I create a persistent node it has some earliest time stamp when it was created which is the time stamp of its initial values for the fields. So usually we will not just create a new node and not do anything with it. We will usually have update steps that also set the fields to some value. But uh here in principle these are split. So if it's just a new allocated node then we're done. Uh the other option for an update step could be that I'm setting some field to a new value and suppose that this is an information field. So not a pointer and in this case um these don't get logs or update uh boxes.

8:34 Maybe this is um it's just a micro optimization one could leave out but let's let's keep it. So um there's there's two step two different cases. If the timestamp the version of the note that we're uh trying to update it has a persistent copy which has a certain version. If that version is the same version we're currently working in that means by and large this node is is new or has only been updated. Now um in this case we can simply overwrite the field value because we're in a way still in the same transaction and so we may change the same field several times in the same operation but because this is within the same version we don't need to keep these updates we only preser persist uh the the version of the data structure after an entire update operation is done. So in this case uh you you simply update in the persistent node.

9:38 And otherwise we create a copy with the new value and time stamp. Okay. uh they called it C of XAR the copy of Xbar. Um in this copy we can set the field to the new value.

10:26 That's a B. Uh, I'm not going to spell it out in more detail. I think this part is easy. The rest of the fields you just copy. Um, right.

10:48 Mentioned this last time. any new copy has to be kept because we may have to update pointers into the old persistent copy to now point to the new copy. So we add this node this new copy to our set s of nodes that we still have to check and this is these newly copied nodes. Um that's what we do for the info fields. Now we also may have an update to a pointer field. So we set in the ephemeral data structure we try to update a pointer. What do we do in the persistent data structure? We try to do the same pointer fields. Sorry. Um, if there is a a copy box in in Xbar left, well, I guess the first is again this same thing.

11:54 If we're still in the current version, no need to um do anything special. Then we set the pointer to Y. Um but that's the uh the unusual case.

12:15 Otherwise we try to put this update in the update box. And then we we add this triple of what was the first first the version then the field value and then the the new value um into one update box and then we're done. Third option uh all of this is not true that means we have to copy. So again where uh we now set the version to now and we set all the fields to the current values but the pointer now has this new value y bar.

13:34 And again because we've created a new note, we have to add the the new copy to the set S. Um, I should say there's there's one extra one extra complication.

14:00 Um, before you create a new copy of a node, you check if there's already a scheduled copy of that node. Maybe there's several updates to the same node and you've already uh created a new node, then you don't use another one. So in all cases uh we can check if this C of Xbar already exists because we haven't yet updated the predecessors, right? So how could this happen? Um there was an update to some node. Uh maybe draw a little picture. So here's our node X and it had all its update boxes already filled. And now there was a further change. So some other note um updated a field here or updated a pointer.

15:10 So we've created this copy C of X bar. Now, some old node said may have a pointer to this node X and it doesn't yet know that we've created this copy because we only do the cleanup after all the update steps. So, it will still point to this this one. So, it could happen that via this pointer from set, we try to do another update here. And so, that's where we use this this chain of pointers. Um there's there's one extra pointer we use to keep um track of these these copies. If we've already created one, we first try to use the update boxes of this node or we try to update the fields of this node. It'll have the version V. So if you write the field another time, it'll just overwrite the field here.

16:08 So we just try to delay making extra copies. It could potentially happen if you do a lot of update steps that even this this new copy overflows then you may have a chain of copies eventually. Um but this is um if if that happens then you also had many update steps. Okay, that was step one. Um the update steps of the update operation.

16:31 Um for step two maybe I can make this bit more space efficient. and since this has to escalate we'll have to do this in the loop. So um again let me stress that we do this after all update steps are done.

17:19 When all the update steps are are complete then we do one round of of fixing predecessors. So while this this set S is not empty, uh we pick one of those. Um this is a copy of some node uh in S I guess. Now this has uh because it's a life node, it stores back pointers. Uh that's another thing that I guess we should do upon the update steps. Uh remember that we kept this d uh sorry this p extra pointers for every node or the number of predecessors p. So whenever we do an update step uh of a pointer field and this is uh always for live pointers I guess. Um we make sure that we also keep track of the backwards pointers.

18:58 I mean this sounds more complicated than it is. If you set a pointer then you have two objects in your hand. One object where you set the pointer to the other object. You have the other object here. So you can set the backward pointer from the other object to where you set the pointer from. This is is a one extra write operation. And this is not one that we cache uh or that we that we log. Remember these are p extra fields that are not used for anything else but for storing um the back pointers. Um and we uh we only keep those for life pointers. So for pointers that go from life objects that might still receive updates to others. So we don't have to keep them updated in in old copies. That's what I'm saying. They they would never be accessed anyways. So in a way it's a simple step, but uh it makes my case distinction here even longer. Uh so maybe it's fine to have it as an extra aside that whenever you actually set the update, make sure that you update the backward pointer.

20:01 Okay. Um if you have your uh your vertex in the copy set then it will have some predecessors set. Again you get those via the backward pointers in constant time.

20:29 And then uh on each of these predecessors, you're essentially doing another field update because you want to set their their pointer field now to the new copy.

20:47 So let's let's suppose that there's just this one pointer field P for now and we set that to the new copy C of X.

21:02 with the understanding that previously we had this point to the original copy of X and so now you update it to the copy. This is an update step that essentially follows the rules from above. Um if this is the current version, you just overwrite it. Uh if it has an update box, you put it there. If it doesn't have space to um lock the update, this may create extra copies of set, one extra copy of set, which may then be added to S, which means while you're shrinking S and uh going through the the predecessors of the newly created nodes, there might be newly created nodes created, newly created copies.

21:53 So this is as above and you might create new copies. That's why we do this in a loop. Um but it will eventually terminate because uh in the worst case we've copied the entire graph and at some point uh we don't increment the version. So at some point all of the updates that we do will run into this first case.

22:27 That's that's the algorithm. So uh an update operation essentially simulates what the ephemeral data structure would have done where I'm trying to do all the update steps locally and if I can't I create a copy at the very end I process the copies so that predecessors of the old versions now point to the new copy. It's conceptually not not super uh not super convoluted even though it has a a bunch of steps. What isn't obvious maybe is why this second step should be fast because occasionally it can be slow right occasionally it might happen that you have to copy a lot of these nodes if for some reason all the update boxes were used already that's why the overall um data structure can only be amvertised as is mentioned in the theorem um [snorts] yeah amortized space and and time So uh it turns it turns the operation time into an amortizers in an amortized guarantee.

23:40 What we have to show is that this amatized step works. because if you go over what we're doing, uh the time is essentially dominated by the space that we use. Whenever we do something that may be uh expensive, then it'll also have triggered extra time, extra space before. there's a few extra update steps that may not uh create extra time but then their number is bounded because uh we can only do updates on these constant number of fields.

24:33 So we'll we'll bound the extra space um that we use for these update operations and again any single operation may trigger a lot of copies. Uh here we'll use that the number of extra uh number of update boxes at least the indigree and because individual update operations could be expensive could create a lot of nodes we'll have to do this in an amortized sense so there'll be a potential function we have to actually created nodes uh new nodes copies and we have the change of some potential function. Now what potential could we use? Um I'm trying to give the intuition first. the the thing that causes expensive copying is if I've used update boxes and on the other hand if I have a lot of nodes that I've created in the past where I had to pay for but now they have a lot of empty update boxes I'm good for a long time so uh the kind of potential I create is just the number of used update boxes this or filled those that I can no longer use because they've already been filled.

26:30 And then we'll see that uh for any operation the amortized cost is uh advertised space cost is constant. So in an update operation, this is um again let me stress not per step but per operation is what the analysis does. Uh we'll have extra space per update step though.

27:11 So let's fix the number of these update steps. Then the goal would be to show that total extra space is is proportional to u right number of update steps. Um also recall that we keep this uh set of newly created nodes.

27:38 Yes. Okay. Um uh during the original update steps let me include the U to make this clear. So these are the update steps that are part of the ephemeral data structure.

28:06 Um how many extra nodes can I possibly have? Well, in the worst case up to you, but let's say we have t new nodes.

28:27 and these are all added to the set s. So, at the beginning of this post-processing step, uh maybe this this should be s0. So, s changes over time. Uh but what I mean is after the original update steps are all done, I will have created a certain number of extra copies. Their number is that's called t. We know that's at most one per update step. We don't escalate there any further. It's a single atomic right. Um and this is precisely the the copied nodes that I still have to take care of in this in this post-processing.

29:14 post-processing. This was the step two from above fixing all the predecessor pointers. Um we may get further copies which is an unclear number. Right? is uh could essentially be everything.

29:44 and what the amortization will have to do is somehow eat up the k. This t is fine. That's bounded by u. We'll expect a cost of proportional to u. But these k this k could be the entire data structure. The actual cost um in terms of new nodes is then just this t + k. That's the overall number of new nodes that I create. Uh they are never destroyed. So they'll stick around for good.

30:25 uh for each new copy in this second step in the post-processing round uh we have a slightly stronger guarantee than otherwise um these updates may go to the same node several times so it's a bit less clear but in the post-processing I'm only doing this one update on a note if it's the predecessor of something and then it gets a pointer field changed if that triggers an update um the note before was full.

31:06 which means in terms of the potential the number of of used filled update boxes. Uh this is only counting in live nodes. For the dead nodes, we don't care. These are uh already dealt with only in life nodes. That's important here. So when a full node dies, it releases this potential. It had uh was at E potential and now it dies. So this this potential is gone.

31:46 Of course, we also create a new node. So we have to change um we have to see what happens there. This new node is empty because it was created in this post-processing step. It hasn't used up any of its update boxes, which means this doesn't contribute to the potential. It's a new life node, but it hasn't have any of the update boxes filled. So, it stays with this drop in potential from having a full node retire.

32:32 And this is for each copy, right? So, uh we get this um k times So there's a good deal of potential released. Unfortunately, that's not the end of the story uh because we also have to update the the pointer. So uh we may use some update boxes in the process of uh setting pointers, right? Um overall we'll have to remove from this set s T + K uh nodes because all of these have been newly created at some point in time and we have to deal with them. Whenever we do that, uh that triggers an update step or a right which may use uh some.

33:52 triggers up to D up to P um update steps and these tend to uh use some update boxes again. So um for each of those may consume up to P boxes. However, um there's a few that we can subtract. we can subtract K again because K of these steps were such that the node overflows uh which means here we we created a copy so we couldn't use an update box that's the whole point why we created this extra copy K times so for each of these steps out of these T plus K steps um there were at least a few cheap ones Okay. Uh so the overall if you combine this with the previous part my notation is a bit improper. This this only is the change in potential for these removals. This is for the copies. Um the overall change in potential from the entire update operation uh is the sum of these two things. So minus E * K plus this term.

35:36 Um let's put the P first. T + K minus K. So in particular um this term K which was the dangerous one now has uh a negative coefficient or non- negative coefficient. Right?

36:00 because the assumption was from above that the number of extra uh slots for pointers E is greater equal than P. So this will be at least minus K plus this term on the on the right. Now this is um this is upper bounded in terms of U. P is a constant and T was at most U the number of updates a number of copies in the update steps. So if we sum up the total costs this will work out.

36:46 The actual cost was T + K. And the change in potential is this. That's still a times, not a minus. And so, uh, the K cancels and what's left is is linear is up upper bounded by U times some constant.

37:11 Okay, I'll I'll leave it with the precise analysis for the space for the running time. The same kind of amortization happens. You have to also count the access operations. Uh they of course contribute to the time, but you don't do anything different there. There's a constant slowdown from looking at the update boxes instead of directly jumping to the value of the field. Uh but the access steps are kind of easy to deal with and the update steps have the same cost as kind of the space you use. So uh that that part is easy. Okay, long long story short, we um we can take any ephemeral data structure if it has if it satisfies these conditions and we can turn it at essentially no overhead into an a partially persistent data structure. Um and you can think about some examples. So maybe let's do this here where we have the conditions stated. What are examples of data structures where this applies?

38:18 How about the two examples we started with with our um simple approaches? One was a balanced binary search tree with any kind of uh balancing mechanism really. It's clearly linked based. It doesn't use anything other than nodes. They have constant degree constant outderee because they have just the child pointers and they also have constant in degree because it's actually one, right? Just the parent points to a node. So clearly any kind of um balanced binary search tree in principle satisfies this. Um if you want to be a bit smarter you can try to improve but this the theorem applies as a black box. So whatever the uh binary search tree does in a constant factor slowdown for the running time you can do the same thing in persistent um with a bit extra space per update step. Now you would have to revisit your favorite binary search trees and see how many write operations they do. So clearly a very bad choice here would be spllay trees because even for accesses they always play things to the root. So they do a ton of writes uh even if you only only read the data.

39:39 So um in principle any any anything goes and applies the theorem applies but the guarantees you get because of the extra space per update step are not that great if your binary search tree writes all the time.

39:55 Okay. Maybe let let me let me say update steps. That's the terminology we used. So here display look at you. What else? Uh we've looked at the doubly linked list is link based uh linked data structure. It has indigree 2. So everything works fine. So you can you can take any operations on such a linked data structure inserts anywhere or deletions and you get persistence for free. And here no strings attached, right? um you can always make a doubly linked list use a constant number of update steps per update operation. So this really works uh without any extra hassles. Uh Fibonacci heaps um is a bit unfair. We didn't cover them proper, right? I only give an overview. Remember that they have to do this uh combination step where you combine the number of trees again to make a um to make the number of trees logarithmic. And the same trick in in quake heeps. By the way, quake heaps is maybe even clearer.

41:23 The nodes are is you could make it as a linkbased data structure and the nodes have bounded in degree. Uh but you need an array during the bucket uh sort and for that array everything dies. And for Fibonacci heaps, so both Fibonacci and Quake heaps have this problem that they use an array.

41:58 Uh for Fibonacci heaps, um apparently you can replace the bucket search, the bucket sort with an array by some clever linked data structure, but then you lose bounded integr. And it seems only at this point that you lose it. Um let me let me continue this for one bit. Um how about LP heaps? Uh the other simpler data structure. Um not the one with quick heaps where you have this in an array. That's not allowed. But if you keep [clears throat] balanced binary search tree of the pivots and for the buckets for the sets you keep a linked list. Everything's node based and the indigree is bounded. So these work again.

42:51 There's another catch with with these that is not in the theorem applies as is. Um there's another catch uh that you can think about for a second.

43:06 Okay, let me finish with a few comments on this. This is basically all I want to show you in terms of technical details about persistence. Uh it turns out the same paper and the same technique can be extended to be fully persistent where you can also change based on any past version. You can do updates and then you fork basically into a a tree of different versions where uh now um history might diverge. uh the construction becomes more complicated because well for one versions are now no longer just numbers they are there's a tree you always have to remember what version did you start with your update operation from um there's a there's a cute trick which um even if you have some arbitrary tree maybe this is your version tree right so every every node is a version um whenever I draw a child edge that means this did an update on this version and then it's a new version of its own. Uh this is a bit tricky to to store if you want surge on the versions and so on. Um an oiler tour essentially walks along the outside of this tree visiting every edge twice and that gives an a linear order of all the versions and you can use that where um to linearize it. And so uh you need that for the accesses to be quick in checking if there's what what's the most recent update to the version I'm trying to read as there have been some most recent right and this is essentially now finding an ancestor in this tree and so this becomes more complicated to do fast and I'm not going to get into how um uh the other point is that we can no longer declare a node dead once it's been copied And so we can't really pack the nodes full of update logs if they're dead because they may receive further updates.

45:08 It turns out that this is this is the easier problem in a way. You just have to somehow leave a bit extra slack in how many update boxes you have. And when you create a note, you don't just copy it and then the new node gets the new version. uh you kind of split the updates between the two so that both of them have a few update boxes left for future updates. Um this I think is it has some similarity to how B trees split a node except that now it's over over time not the key domain. So this is a everything gets a bit more complicated. Um but the the full details in in the paper are worked out and show that you can still make it make it work. Uh the main reason why I'm I'm not getting into it more is that I'm I'm not sure there's a very convincing application of full persistence whereas partial persistence seems to be useful for various reasons including this planer point location and and other other algorithmic tricks. Uh the other question you might ask after seeing these two constructions that essentially take an arbitrary data structure apart from these little constraints and turn it into a persistent one. Is there anything um worth worth studying there?

46:25 And uh there's been a lot of work despite this general transformation uh because in many cases you can improve what the general transformation gives you a bit further. Um for binary search trees, I hinted at this earlier that it's fine in principle. works out of the box, but many binary search trees tend to do a bit bit too many update steps in their original version and you can improve what the transformation gives you by first working out to save on on writes in in binary search trees. Uh, and then there's been a lot of work on external memory data structures. It's kind of I I hope to get to some some more on this proper later in the module. So we haven't really talked about it. Uh there the game is different. You're not really interested in counting individual nodes but blocks of memory and they need to somehow be kept local together. Also updates are counted differently. You're only interested in memory transfers. And so there it doesn't seem to be so automatic. The transformation gives you something but it's not already optimal.

47:33 And there's uh maybe maybe one of the most famous uh contributions of of our colleague Banhhat Sezega is is essentially like uh in this direction. It's a partially persistent B tree in our terminology. Uh except that in the database world they call this multi version. It's the same thing but has a different name because it was invented for a slightly different purpose and by different people sometimes as well. Um then speaking about B trees, you can also make these fully persistent where you now you use specific properties of B trees and not try to make a fully general transformation.

48:14 So we'll probably see more more results on specific data structures along these lines because there's no no obvious bound why you cannot further improve.

48:33 one last comment. Uh, I mentioned that LP heaps um as they are work fine in that you can apply the transformation to make them partially persistent or maybe even fully persistent. Uh however there's um there's a subtlety that comes uh entirely from how the whole setup of persistence is defined that we didn't have to worry about before. Uh partial persistence in principle works fine even if the guarantees for your data structures are amvertised as in the case of LP heaps. But think about what this means. I can now potentially go uh with updates to a certain point in my data structure where I'm in a in a bad state of high potential where the next update or the next query could be very expensive. I cannot in general rule this out because that's the essence of an amortized data structure. It may occasionally be in a state where the next uh where the next update where the next query is expensive. Now, if I'm in a persistent world, I have to keep that version around and a mean user could keep asking me queries at the same version and essentially break the amortized bound because you can no longer rely on on this sequence of operations to somehow be able to change the data structure. It may by by sheer malice um you may be forced to go through the expensive step each time when you do this uh this operation because someone gave you the bad version over and over again. I don't think there's any way out of this uh in in full generality.

50:19 Uh you can try to work your way around it. It's also less problematic for partial persistence if only the amortization is on the updates. Right? If uh if reading the data structure is always worst case bounded, then you're in good shape. Uh unfortunately for LP heaps, this is not really true. Um you would have to properly define what a readonly operation there really means. U but I could I could define an operation that reads the minimum by scanning the leftmost interval uh or the leftmost set but doesn't change it. that operation over the course of many operations and mixed with with real queries uh wouldn't be too expensive um because in an ephemeral data structure I could make that read still split even if it doesn't remove the minimum I can make it make progress in splitting of the intervals uh but in a persistent data structure I can't really do that and so I might be stuck in a place where this leftmost set is really big and some annoying user comes along and keeps asking me for the minimum of this set. So I can't without further changes rule out that the bounds uh but the running time I get for operations are a bit meaningless unless you do some extra work. Amortization is a bit problematic and so this is even more true for full persistence I guess.

51:47 Uh but this is something you should just keep in mind because it totally does not show up in the transformation or the proof that we've done. Per update step everything is fine and per access step everything's fine.

52:06 Okay with that slight uh cautionary warning let's conclude the persistence chapter.