Content deleted Content added
Reverting edit(s) by 134.117.247.196 (talk) to rev. 1189764739 by 2A01:4B00:844D:E800:ED23:9DA8:8859:A891: Not providing a reliable source (RW 16.1) |
m Added information on partially persistent data structure |
||
Line 10:
==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 [[Total order|linear ordering]] among each version of the data structure.<ref>{{Citation|last1=Conchon|first1=Sylvain|chapter=Semi-persistent Data Structures|pages=322–336|publisher=Springer Berlin Heidelberg|isbn=9783540787389|last2=Filliâtre|first2=Jean-Christophe|doi=10.1007/978-3-540-78739-6_25|title=Programming Languages and Systems|volume=4960|series=Lecture Notes in Computer Science|year=2008|doi-access=free}}</ref> In the fully persistent model, both updates and queries are allowed on any version of the data structure. In some cases the [[Computer performance|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)|rope data structure]].<ref>{{Cite book|title=RRB-Trees: Efficient Immutable Vectors|last=Tiark|first=Bagwell, Philip Rompf|date=2011|oclc=820379112}}</ref> 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.<ref>{{Citation|last1=Brodal|first1=Gerth Stølting|title=Algorithms – ESA 2006|date=2006|series=Lecture Notes in Computer Science|pages=172–183|publisher=Springer Berlin Heidelberg|isbn=9783540388753|last2=Makris|first2=Christos|last3=Tsichlas|first3=Kostas|chapter=Purely Functional Worst Case Constant Time Catenable Sorted Lists |volume=4168 |doi=10.1007/11841036_18|citeseerx=10.1.1.70.1493}}</ref>
== 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.<ref>{{Cite journal |last=Lenhof |first=Hans-Peter |last2=Smid |first2=Michiel |date=1994 |title=Using persistent data structures for adding range restrictions to searching problems |url=http://dx.doi.org/10.1051/ita/1994280100251 |journal=RAIRO - Theoretical Informatics and Applications |volume=28 |issue=1 |pages=25–49 |doi=10.1051/ita/1994280100251 |issn=0988-3754}}</ref>
==Techniques for preserving previous versions==
Line 196 ⟶ 209:
==References==
{{Reflist}}
<references
==External links==
| |||