Persistent data structure: Difference between revisions

Revision as of 12:47, 30 November 2023

Revision as of 02:35, 11 December 2023

Line 2:

{{Distinguish|Persistent storage}}

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 object|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.<ref name="Driscoll">{{Cite book |vauthors=Driscoll JR, Sarnak N, Sleator DD, Tarjan RE |date=1986 |title=Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86 |year=1986 |chapter=Making data structures persistent |isbn=978-0-89791-193-1 |doi=10.1145/12130.12142 |pages=109–121|citeseerx=10.1.1.133.4630 |s2cid=364871 }}</ref>

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''.<ref name="kaplan2">{{Cite journal|author=Kaplan, Haim|year=2001|title=Persistent data structures|url=http://www.math.tau.ac.il/~haimk/papers/persistent-survey.ps|journal=Handbook on Data Structures and Applications}}</ref>

Line 65:

===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

Line 73:

*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})</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})</math>. Each access operation can be done in <math>O(Log(d))</math> and there are <math>m</math> 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 <math>n</math> sequence of CREATE-NODE, CHANGE-EDGE and CHANGE-LABEL in <math>O(n\cdot d^{2})+m\cdot O(Log(d))</math>.

==Applications of persistent data structures==

Line 182:

=== Scala ===

The Scala programming language promotes the use of persistent data structures for implementing programs using "Object-Functional Style".<ref>{{Cite news|url=https://blog.codecentric.de/en/2015/08/essence-of-object-functional-programming-practical-potential-of-scala/|title=The Essence of Object-Functional Programming and the Practical Potential of Scala - codecentric AG Blog|date=2015-08-31|work=codecentric AG Blog|access-date=2018-10-23|language=en-US}}</ref> Scala contains implementations of many persistent data structures including linked lists, [[red–black tree]]s, as well as persistent hash array mapped tries as introduced in Clojure.<ref>{{Citation|last=ClojureTV|title=Extreme Cleverness: Functional Data Structures in Scala - Daniel Spiewak|date=2013-01-07|url=https://www.youtube.com/watch?v=pNhBQJN44YQ|access-date=2018-10-23}}{{cbignore}}{{Dead YoutubeYouTube linkslink|date=February 2022}}</ref>

==Garbage collection==