Making data structures persistent
type: Item
instance of: scholarly article
title: Making data structures persistent
zbMATH Open document ID: 0667.68026
DOI: 10.1016/0022-0000(89)90034-2
author: S. H. Smith
published in: Journal of Computer and System Sciences
publication date: 1989-01-01T00:00:00Z
review text: Making a change in an ordinary data structure destroys the old version, leaving only the new one. This paper investigates the problem of realizing persistent data structures in the sense that all the versions in the history of the data structure are available for use. Two kind of persistence are identified: partial persistence in which only the newest version may be updated and fully persistence in which an update operation may apply to any version. The authors study the case of linked data structures for which they propose two paradigms for making them persistent. These techniques are used to devise persistent forms of binary search trees with efficient implementations of the access, insertion and deletion operations.
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68W99
zbMATH DE Number: 4092741
zbMATH Keywords: persistent data structures
zbMATH Keywords: binary search trees
Wikidata QID: Q30052803
reviewed by: Marius Zimand
MaRDI profile type: Publication
full work available at URL: 0022-0000(89)90034-2
OpenAlex ID: W4213048098
cites work: Organization and maintenance of large ordered indexes
cites work: Decomposable searching problems I. Static-to-dynamic transformation
cites work: On the average number of rebalancing operations in weight-balanced trees
cites work: Design and Analysis of a Data Structure for Representing Sorted Lists
cites work: Filtering Search: A New Approach to Query-Answering
cites work: How to search in history
cites work: Q3687756
cites work: Fractional cascading. I: A data structuring technique
cites work: Searching and storing similar lists
cites work: Q3907100
cites work: A new data structure for representing sorted lists
cites work: An applicative random-access stack
cites work: Binary Search Trees of Bounded Balance
cites work: Q3707420
cites work: Updating a balanced search tree in 0(1) rotations
cites work: Amortized Computational Complexity
cites work: Maintaining order in a generalized linked list
cites work: AVL-trees for localized search
description: scientific article; zbMATH DE number 4092741