Optimal worst-case fully persistent arrays


Abstract:

We describe an implementation of fully persistent arrays with worst-case O(log log m) time complexity of update and lookup, and O(n+m) space complexity, where n is the size of the array and m is the number of modifications to the array.

This lookup complexity is shown to be asymptotically optimal even for partially persistent arrays in the cell probe model using recent results of Patrascu and Thorup. Hence there cannot exist any persistent array, persistent hashtable nor any persistent graph with constant-time operations.

We also improve the complexity of update and lookup to O(log log min(n, m)) and show how to augment the algorithm to cooperate with the garbage collector to free unreachable data.

The paper was presented at TFP 2009, but was not accepted to the Proceedings. The draft paper is available as PDF.
Back