TY - JOUR
T1 - Making data structures persistent
AU - Driscoll, James R.
AU - Sarnak, Neil
AU - Sleator, Daniel D.
AU - Tarjan, Robert E.
N1 - Funding Information:
* A condensed, preliminary version of this paper was presented at the Eighteenth Annual ACM Symposium on Theory of Computing, Berkeley, California, May 28-30, 1986. + Current address: Computer Science Department, University of Colorado, Boulder, Colorado 80309. * Research partially supported by National Science Foundation Grant DCR 8605962.
PY - 1989/2
Y1 - 1989/2
N2 - This paper is a study of persistence in data structures. Ordinary data structures are ephemeral in the sense that a change to the structure destroys the old version, leaving only the new version available for use. In contrast, a persistent structure allows access to any version, old or new, at any time. We develop simple, systematic, and efficient techniques for making linked data structures persistent. We use our techniques to devise persistent forms of binary search trees with logarithmic access, insertion, and deletion times and O(1) space bounds for insertion and deletion.
AB - This paper is a study of persistence in data structures. Ordinary data structures are ephemeral in the sense that a change to the structure destroys the old version, leaving only the new version available for use. In contrast, a persistent structure allows access to any version, old or new, at any time. We develop simple, systematic, and efficient techniques for making linked data structures persistent. We use our techniques to devise persistent forms of binary search trees with logarithmic access, insertion, and deletion times and O(1) space bounds for insertion and deletion.
UR - http://www.scopus.com/inward/record.url?scp=0024606010&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0024606010&partnerID=8YFLogxK
U2 - 10.1016/0022-0000(89)90034-2
DO - 10.1016/0022-0000(89)90034-2
M3 - Article
AN - SCOPUS:0024606010
SN - 0022-0000
VL - 38
SP - 86
EP - 124
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
IS - 1
ER -