Persistent data structure: Difference between revisions

Revision as of 13:57, 20 June 2025

Latest revision as of 07:10, 21 June 2025

(2 intermediate revisions by one other user not shown)

Line 44:

===A combination===

Driscoll, Sarnak, [[Daniel Sleator|Sleator]], [[Robert Tarjan|Tarjan]] came up<ref name=Driscoll /> with a way to combine the techniques of fat nodes and path copying, achieving O(1) access slowdown and O(1) modificationamortized overhead in space and time complexityper modification. Their method assumes a linked data structure with at most ''d'' incoming pointers to each node, where ''d'' is a known constant.

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.

Line 88:

*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 <math>d+1</math> credits are transformed to the new table in addition to the one credit acquired from calling the CHANGE-EDGE. So in total we have <math>d+2</math> 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 {{mvar|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 <math>n_{1}</math> calls to CREATE_NODE and <math>n_{2}</math> calls to CHANGE_EDGE will result in the creation of <math>2\cdot n_{1}+n_{2}</math> tables. Since each table has size <math>O(d)</math> without taking into account the recursive calls, then filling in a table requires <math>O(d^{2}dc)</math> 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 <math>O(d^{2}dc)</math>. Each access operation can be done in <math>O(\log(d))</math> and there are {{mvar|m}} edge and label operations, thus it requires <math>m\cdot O(\log(d))</math>. We conclude that There exists a data structure that can complete any {{mvar|n}} sequence of CREATE-NODE, CHANGE-EDGE and CHANGE-LABEL and ''m'' access operations in <math>O(n\cdot d^{2}dc)+m\cdot O(\log(d))</math>.

==Applications of persistent data structures==