In computing, a persistent data structure or not ephemeral data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure. The term was introduced in Driscoll, Sarnak, Sleator, and Tarjan's 1986 article.^[1]

A data structure is partially persistent if all versions can be accessed but only the newest version can be modified. The data structure is fully persistent if every version can be both accessed and modified. If there is also a meld or merge operation that can create a new version from two previous versions, the data structure is called confluently persistent. Structures that are not persistent are called ephemeral.^[2]

These types of data structures are particularly common in logical and functional programming,^[2] as languages in those paradigms discourage (or fully forbid) the use of mutable data.

Partial versus full persistence

In the partial persistence model, a programmer may query any previous version of a data structure, but may only update the latest version. This implies a linear ordering among each version of the data structure.^[3] In the fully persistent model, both updates and queries are allowed on any version of the data structure. In some cases the performance characteristics of querying or updating older versions of a data structure may be allowed to degrade, as is true with the rope data structure.^[4] In addition, a data structure can be referred to as confluently persistent if, in addition to being fully persistent, two versions of the same data structure can be combined to form a new version which is still fully persistent.^[5]

Partially persistent data structure

A type of data structure where user may query any version of the structure but may only update the latest version.

An ephermeral data structure can be converted to partially persistent data structure using a few techniques.

One of the technique is by using randomized version of Van Emde Boas Tree which is created using dynamic perfect hashing. This data structure is created as follows:

• A stratified tree with m elements is implemented using dynamic perfect hashing.
• The tree is pruned by dividing the m elements into buckets of size log(log n) such that the elements of bucket 1 is smaller than the elements of bucket 2 and so on.
• The maximal element in each bucket is stored in the stratified tree and each bucket is stored in the structure as an unordered linked list.

The size of this data structure is bounded by the number of elements stored in the structure that is O(m). The insertion of a new maximal element is done in constant O(1) expected and amortized time. Finally query to find an element can be done in this structure in O(log(log n)) worst-case time.^[6]

Techniques for preserving previous versions

Copy-on-write

One method for creating a persistent data structure is to use a platform provided ephemeral data structure such as an array to store the data in the data structure and copy the entirety of that data structure using copy-on-write semantics for any updates to the data structure. This is an inefficient technique because the entire backing data structure must be copied for each write, leading to worst case O(n·m) performance characteristics for m modifications of an array of size n.^{[citation needed]}

Fat node

The fat node method is to record all changes made to node fields in the nodes themselves, without erasing old values of the fields. This requires that nodes be allowed to become arbitrarily “fat”. In other words, each fat node contains the same information and pointer fields as an ephemeral node, along with space for an arbitrary number of extra field values. Each extra field value has an associated field name and a version stamp which indicates the version in which the named field was changed to have the specified value. Besides, each fat node has its own version stamp, indicating the version in which the node was created. The only purpose of nodes having version stamps is to make sure that each node only contains one value per field name per version. In order to navigate through the structure, each original field value in a node has a version stamp of zero.

Complexity of fat node

With using fat node method, it requires O(1) space for every modification: just store the new data. Each modification takes O(1) additional time to store the modification at the end of the modification history. This is an amortized time bound, assuming modification history is stored in a growable array. At access time, the right version at each node must be found as the structure is traversed. If "m" modifications were to be made, then each access operation would have O(log m) slowdown resulting from the cost of finding the nearest modification in the array.

Path copying

With the path copying method a copy of all nodes is made on the path to any node which is about to be modified. These changes must then be cascaded back through the data structure: all nodes that pointed to the old node must be modified to point to the new node instead. These modifications cause more cascading changes, and so on, until the root node is reached.

Complexity of path copying

With m modifications, this costs O(log m) additive lookup time. Modification time and space are bounded by the size of the longest path in the data structure and the cost of the update in the ephemeral data structure. In a Balanced Binary Search Tree without parent pointers the worst case modification time complexity is O(log n + update cost). However, in a linked list the worst case modification time complexity is O(n + update cost).

A combination

Driscoll, Sarnak, Sleator, Tarjan came up^[1] with a way to combine the techniques of fat nodes and path copying, achieving O(1) access slowdown and O(1) modification space and time complexity.

In each node, one modification box is stored. This box can hold one modification to the node—either a modification to one of the pointers, or to the node's key, or to some other piece of node-specific data—and a timestamp for when that modification was applied. Initially, every node's modification box is empty.

Whenever a node is accessed, the modification box is checked, and its timestamp is compared against the access time. (The access time specifies the version of the data structure being considered.) If the modification box is empty, or the access time is before the modification time, then the modification box is ignored and only the normal part of the node is considered. On the other hand, if the access time is after the modification time, then the value in the modification box is used, overriding that value in the node.

Modifying a node works like this. (It is assumed that each modification touches one pointer or similar field.) If the node's modification box is empty, then it is filled with the modification. Otherwise, the modification box is full. A copy of the node is made, but using only the latest values. The modification is performed directly on the new node, without using the modification box. (One of the new node's fields is overwritten and its modification box stays empty.) Finally, this change is cascaded to the node's parent, just like path copying. (This may involve filling the parent's modification box, or making a copy of the parent recursively. If the node has no parent—it's the root—it is added the new root to a sorted array of roots.)

With this algorithm, given any time t, at most one modification box exists in the data structure with time t. Thus, a modification at time t splits the tree into three parts: one part contains the data from before time t, one part contains the data from after time t, and one part was unaffected by the modification.

Complexity of the combination

Time and space for modifications require amortized analysis. A modification takes O(1) amortized space, and O(1) amortized time. To see why, use a potential function ϕ, where ϕ(T) is the number of full live nodes in T . The live nodes of T are just the nodes that are reachable from the current root at the current time (that is, after the last modification). The full live nodes are the live nodes whose modification boxes are full.

Each modification involves some number of copies, say k, followed by 1 change to a modification box. Consider each of the k copies. Each costs O(1) space and time, but decreases the potential function by one. (First, the node to be copied must be full and live, so it contributes to the potential function. The potential function will only drop, however, if the old node isn't reachable in the new tree. But it is known that it isn't reachable in the new tree—the next step in the algorithm will be to modify the node's parent to point at the copy. Finally, it is known that the copy's modification box is empty. Thus, replaced a full live node has been replaced with an empty live node, and ϕ goes down by one.) The final step fills a modification box, which costs O(1) time and increases ϕ by one.

Putting it all together, the change in ϕ is Δϕ =1− k. Thus, the algorithm takes O(k +Δϕ)= O(1) space and O(k +Δϕ +1) = O(1) time

Generalized form of persistence

Path copying is one of the simple methods to achieve persistency in a certain data structure such as binary search trees. It is nice to have a general strategy for implementing persistence that works with any given data structure. In order to achieve that, we consider a directed graph G. We assume that each vertex v in G has a constant number c of outgoing edges that are represented by pointers. Each vertex has a label representing the data. We consider that a vertex has a bounded number d of edges leading into it which we define as inedges(v). We allow the following different operations on G.

• CREATE-NODE(): Creates a new vertex with no incoming or outgoing edges.
• CHANGE-EDGE(v, i, u): Changes the i^th edge of v to point to u
• CHANGE-LABEL(v, x): Changes the value of the data stored at v to x

Any of the above operations is performed at a specific time and the purpose of the persistent graph representation is to be able to access any version of G at any given time. For this purpose we define a table for each vertex v in G. The table contains c columns and ${\displaystyle d+1}$ rows. Each row contains in addition to the pointers for the outgoing edges, a label which represents the data at the vertex and a time t at which the operation was performed. In addition to that there is an array inedges(v) that keeps track of all the incoming edges to v. When a table is full, a new table with ${\displaystyle d+1}$ rows can be created. The old table becomes inactive and the new table becomes the active table.

CREATE-NODE

A call to CREATE-NODE creates a new table and set all the references to null

CHANGE-EDGE

If we assume that CHANGE-EDGE(v, i, u) is called, then there are two cases to consider.

• There is an empty row in the table of the vertex v: In this case we copy the last row in the table and we change the ith edge of vertex v to point to the new vertex u
• Table of the vertex v is full: In this case we need to create a new table. We copy the last row of the old table into the new table. We need to loop in the array inedges(v) in order to let each vertex in the array point to the new table created. In addition to that, we need to change the entry v in the inedges(w) for every vertex w such that edge v,w exists in the graph G.

CHANGE-LABEL

It works exactly the same as CHANGE-EDGE except that instead of changing the i^th edge of the vertex, we change the i^th label.

Efficiency of the generalized persistent data structure

In order to find the efficiency of the scheme proposed above, we use an argument defined as a credit scheme. The credit represents a currency. For example, the credit can be used to pay for a table. The argument states the following:

• The creation of one table requires one credit
• Each call to CREATE-NODE comes with two credits
• Each call to CHANGE-EDGE comes with one credit

The credit scheme should always satisfy the following invariant: Each row of each active table stores one credit and the table has the same number of credits as the number of rows. Let us confirm that the invariant applies to all the three operations CREATE-NODE, CHANGE-EDGE and CHANGE-LABEL.

• CREATE-NODE: It acquires two credits, one is used to create the table and the other is given to the one row that is added to the table. Thus the invariant is maintained.
• CHANGE-EDGE: There are two cases to consider. The first case occurs when there is still at least one empty row in the table. In this case one credit is used to the newly inserted row. The second case occurs when the table is full. In this case the old table becomes inactive and the ${\displaystyle d+1}$ credits are transformed to the new table in addition to the one credit acquired from calling the CHANGE-EDGE. So in total we have ${\displaystyle d+2}$ credits. One credit will be used for the creation of the new table. Another credit will be used for the new row added to the table and the d credits left are used for updating the tables of the other vertices that need to point to the new table. We conclude that the invariant is maintained.
• CHANGE-LABEL: It works exactly the same as CHANGE-EDGE.

As a summary, we conclude that having ${\displaystyle n_{1}}$ calls to CREATE_NODE and ${\displaystyle n_{2}}$ calls to CHANGE_EDGE will result in the creation of ${\displaystyle 2\cdot n_{1}+n_{2}}$ tables. Since each table has size ${\displaystyle O(d)}$ without taking into account the recursive calls, then filling in a table requires ${\displaystyle O(d^{2})}$ where the additional d factor comes from updating the inedges at other nodes. Therefore, the amount of work required to complete a sequence of operations is bounded by the number of tables created multiplied by ${\displaystyle O(d^{2})}$. Each access operation can be done in ${\displaystyle O(Log(d))}$ and there are ${\displaystyle m}$ edge and label operations, thus it requires ${\displaystyle m\cdot O(Log(d))}$. We conclude that There exists a data structure that can complete any ${\displaystyle n}$ sequence of CREATE-NODE, CHANGE-EDGE and CHANGE-LABEL in ${\displaystyle O(n\cdot d^{2})+m\cdot O(Log(d))}$.

Applications of persistent data structures

Next element search or point location

One of the useful applications that can be solved efficiently using persistence is the Next Element Search. Assume that there are ${\displaystyle n}$ non intersecting line segments that don't cross each other that are parallel to the x-axis. We want to build a data structure that can query a point ${\displaystyle p}$ and return the segment above ${\displaystyle p}$ (if any). We will start by solving the Next Element Search using the naïve method then we will show how to solve it using the persistent data structure method.

Naïve method

We start with a vertical line segment that starts off at infinity and we sweep the line segments from the left to the right. We take a pause every time we encounter an end point of these segments. The vertical lines split the plane into vertical strips. If there are ${\displaystyle n}$ line segments then we can get ${\displaystyle 2\cdot n+1}$ vertical strips since each segment has ${\displaystyle 2}$ end points. No segment begins and ends in the strip. Every segment either it doesn't touch the strip or it completely crosses it. We can think of the segments as some objects that are in some sorted order from top to bottom. What we care about is where the point that we are looking at fits in this order. We sort the endpoints of the segments by their ${\displaystyle x}$ coordinate. For each strip ${\displaystyle s_{i}}$, we store the subset segments that cross ${\displaystyle s_{i}}$ in a dictionary. When the vertical line sweeps the line segments, whenever it passes over the left endpoint of a segment then we add it to the dictionary. When it passes through the right endpoint of the segment, we remove it from the dictionary. At every endpoint, we save a copy of the dictionary and we store all the copies sorted by the ${\displaystyle x}$ coordinates. Thus we have a data structure that can answer any query. In order to find the segment above a point ${\displaystyle p}$, we can look at the ${\displaystyle x}$ coordinate of ${\displaystyle p}$ to know which copy or strip it belongs to. Then we can look at the ${\displaystyle y}$ coordinate to find the segment above it. Thus we need two binary searches, one for the ${\displaystyle x}$ coordinate to find the strip or the copy, and another for the ${\displaystyle y}$ coordinate to find the segment above it. Thus the query time takes ${\displaystyle O(Log(n))}$. In this data structure, the space is the issue since if we assume that we have the segments structured in a way such that every segment starts before the end of any other segment, then the space required for the structure to be built using the naïve method would be ${\displaystyle O(n^{2})}$. Let us see how we can build another persistent data structure with the same query time but with a better space.

Persistent data structure method

We can notice that what really takes time in the data structure used in the naïve method is that whenever we move from a strip to the next, we need to take a snap shot of whatever data structure we are using to keep things in sorted order. We can notice that once we get the segments that intersect ${\displaystyle s_{i}}$, when we move to $$Zdroj:https://en.wikipedia.org?pojem=Persistent_data_structure
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.