On the dynamization of data structures
type: Item
instance of: scholarly article
title: On the dynamization of data structures
zbMATH Open document ID: 0632.68025
DOI: 10.1007/BF01934693
author: N. S. V. Rao
author: Vijay K. Vaishnavi
author: S. S. Iyengar
published in: BIT
publication date: 1988-01-01T00:00:00Z
review text: We present a simple dynamization method that preserves the query and storage costs of a static data structure and ensures reasonable update costs. In this method, the majority of data elements are maintained in a single data structure, and the updates are handled using ``smaller'' auxiliary data structures. We analyze the query, storage, and amortized update costs for the dynamic version of a static data structure in terms of a function f, such that \(f(n)<n\), that bounds the sizes of the auxiliary data structures (where n is the number of elements in the data structure). The conditions on f for minimal (with respect to asymptotic upper bounds) amortized update costs are then obtained. The proposed method is shown to be particularly suited for the cases where the merging of two data structures is more efficient than building the resultant data structure from scratch. Its effectiveness is illustrated by applying it to a class of data structures that have linear merging cost; this class consists of data structures such as Voronoi diagrams, K-d trees, quadtrees, multiple attribute trees, etc.
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 4028881
zbMATH Keywords: amortized insertion and deletion costs
zbMATH Keywords: query and storage costs
zbMATH Keywords: update costs
zbMATH Keywords: merging of two data structures
zbMATH Keywords: merging cost
zbMATH Keywords: Voronoi diagrams
zbMATH Keywords: K- d trees
zbMATH Keywords: quadtrees
zbMATH Keywords: multiple attribute trees
MaRDI profile type: Publication
cites work: Q3219753
cites work: Q3694703
full work available at URL: https://doi.org/10.1007/bf01934693
OpenAlex ID: W2076407808
description: scientific article; zbMATH DE number 4028881