18
$\begingroup$

Persistent data structures are immutable data structures. Operations on them return a new "copy" of the data structure, but altered by the operation; the old data structure remains unchanged though. Efficiency is generally accomplished by sharing some of the underlying data, and avoiding full copying of the data structure.

Questions:

  • Are there results about classes of data structures that can be made to be persistent (while keeping the same or very similar complexities)?

  • Can all data structures be made persistent (while keeping the same or very similar complexities)?

  • Are any data structures known to be unable to be made persistent (while keeping the same or very similar complexities)?

$\endgroup$
  • 1
    $\begingroup$ You can't make a vector persistent with preserved O(1) complexity for accessing a random element. $\endgroup$ – smossen Nov 22 '13 at 20:38
  • $\begingroup$ Possibly relevant: What are the outstanding questions in purely functional data structures?. $\endgroup$ – Realz Slaw Nov 22 '13 at 20:41
  • 2
    $\begingroup$ @smossen can you prove that? $\endgroup$ – Realz Slaw Nov 22 '13 at 20:42
  • 1
    $\begingroup$ Your first question is a very broad question. There are many results on the topic of data structures that can be made persistent. One could write an entire book on the subject, and some folks have: for instance, Okasaki's book is a classic on the subject. Have you done some research on this topic? Can you narrow down the question? As it stands, I suspect it might be too broad to be a good fit for this site. Maybe split out the 3rd question to a separate question? $\endgroup$ – D.W. Nov 22 '13 at 20:52
  • $\begingroup$ @Realz Slaw: I can't prove it formally, but I think it is common sense. O(1) access to elements in vectors (including hash tables) depends on fixed time for address decoding on a given hardware. Persistence adds one or two dimensions in addition to the vector index. But hardware addresses are still one dimensional. $\endgroup$ – smossen Nov 22 '13 at 20:54
22
$\begingroup$

Positive result: persistence does not cost too much. One can show that every data structure can be made fully persistent with at most a $O(\lg n)$ slowdown.

Proof: You can take an array and make it persistent using standard data structures (e.g., a balanced binary tree; see the end of this answer for a bit more detail). This incurs a $O(\lg n)$ slowdown: each array access takes $O(\lg n)$ time with the persistent data structure, instead of $O(1)$ time for the non-persistent array. Now take any imperative algorithm whose running time in the RAM model is $O(f(n))$, where $n$ denotes the amount of memory used. Represent all of memory as one big array (with $n$ elements), and make it persistent using a persistent map. Each step of the imperative algorithm incurs at most a $O(\lg n)$ slowdown, so the total running time is $O(f(n) \lg n)$.

Apparently it is possible to do a bit better: apparently one can reduce the slowdown factor to $O(\lg \lg n)$ (expected, amortized time), using the techniques in the Demaine paper cited below -- but I am not familiar with the details of that work, so I cannot vouch for this myself. Thanks to jbapple for this observation.


Negative result: you cannot avoid some slowdown, for some data structures. To answer your third question, there exist data structures where it is known that making them persistence introduces some slowdown.

In particular, consider an array of $n$ elements. Without persistence, each array access takes $O(1)$ time (in the RAM model). With persistence, it has apparently been shown that there is no way to build a persistent array with $O(1)$ worst-case complexity for accessing a random element. In particular, there is apparently a lower bound showing that fully persistent arrays must have $\Omega(\lg \lg n)$ access time. This lower bound is asserted on p.3 of the following paper:

The lower bound is attributed to Mihai Patrascu, but there is no citation to a source that gives the details of the proof of this asserted lower bound.


A rich area of research. If we take an arbitrary data structure or algorithm, it's a bit of a delicate question whether you can make it persistent with at most $O(1)$ slowdown or not. I don't know of any general classification theorem. However, there is a lot of research into ways to make specific data structures persistent, in an efficient way.

There is also a strong connection with functional programming languages. In particular, every data structure that can be implemented in a purely functional way (with no mutations) is already a persistent data structure. (The converse is not necessarily the case, alas.) If you want to squint your eyes, you could take this as some weak sort of partial classification theorem: if it is implementable in a purely functional programming language with the same time bounds as in an imperative language, then there is a persistent data structure with the same time bounds as the non-persistent one. I realize this probably isn't what you were looking for -- it is mostly just a trivial re-phrasing of the situation.


How to make a persistent array. I won't try to describe the construction for how to build a fully persistent array with $O(\lg n)$ worst-case access time. However, the basic ideas are not too complicated, so I'll summarize the essence of the ideas.

The basic idea is that we can take any binary tree data structure, and make it persistent using a technique called path copying. Let's say we have a binary tree, and we want to modify the value in some leaf $\ell$. However, for persistence, we don't dare modify the value in that leaf in place. Instead, we make a copy of that leaf, and modify the value in the copy. Then, we make a copy of its parent, and change the appropriate child pointer in the copy to point to the new leaf. Continue in this way, cloning each node on the path from the root to the leaf. If we want to modify a leaf at depth $d$, this requires copying $d$ nodes.

If we have a balanced binary tree has $n$ nodes, then all leaves have depth $O(\lg n)$, so this operation on the binary tree takes $O(\lg n)$ time. There are some details I'm skipping -- to achieve $O(\lg n)$ worst-case time, we may need to rebalance the tree to ensure it remains balanced -- but this gives the gist of it.

You can find more explanations, with pretty pictures, at the following resources:

That will give you the main idea. There are extra details to take care of, but the details are out of scope for this question. Fortunately, this is all standard stuff, and there is lots of information available in the literature on how to build such data structures. Feel free to ask a separate question if the above resources aren't enough and you want more information about the details of building a persistent array data structure.

$\endgroup$
  • $\begingroup$ I don't really understand the first paragraph, how would I go about making an array persistent using a red-black tree? $\endgroup$ – G. Bach Nov 23 '13 at 0:56
  • $\begingroup$ @G.Bach, there's a pretty good explanation in the sections labelled "Binary search trees" and "Random-access structures" (specifically, the tree method) at toves.org/books/persist/index.html. For another nice description, see netcode.ru/dotnet/?artID=6592#BinaryTrees and some of the subsequent sections. That will give you the main idea. The details are out of scope for this question, but this is all standard stuff; I encourage you to ask a separate question if you want more information about how to build such a data structure. $\endgroup$ – D.W. Nov 23 '13 at 3:19
  • 4
    $\begingroup$ Good answer, D.W. You can bring the time bound down to (expected amortized) $O(\lg \lg n)$. See Demaine et al.'s "Confluently Persistent Tries for Efficient Version Control" $\endgroup$ – jbapple Nov 23 '13 at 3:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.