Making data structures persistent

James R. Driscoll, Neil Sarnak, Daniel D. Sleator, Robert E. Tarjan

Research output: Contribution to journalArticle

390 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)86-124
Number of pages39
JournalJournal of Computer and System Sciences
Volume38
Issue number1
DOIs
StatePublished - Feb 1989

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Making data structures persistent'. Together they form a unique fingerprint.

Cite this