On the dynamization of data structures

DOI10.1007/BF01934693MaRDI QIDQ1095647zbMATH OpenOpenAlexFDO

Authors N. S. V. Rao, Vijay K. Vaishnavi, S. S. Iyengar

Publication date 1988

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01934693

zbMATH Keywords

amortized insertion and deletion costsK- d treesmerging costmerging of two data structuresmultiple attribute treesquadtreesquery and storage costsupdate costsVoronoi diagrams

Mathematics Subject Classification ID

Data structures (68P05)

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.

Recommendations

• Data structures for mergeable trees
• Dynamic Trees and Dynamic Point Location
• Dynamizing static algorithms, with applications to dynamic trees and history independence
• Towards an optimal method for dynamic planar point location
• Dynamic deferred data structuring

Cited in

(14)

• Efficient splitting and merging algorithms for order decomposable problems.
• Union-copy structures and dynamic segment trees
• scientific article; zbMATH DE number 3852432 (Why is no real title available?)
• scientific article; zbMATH DE number 3864511 (Why is no real title available?)
• scientific article; zbMATH DE number 17540 (Why is no real title available?)
• scientific article; zbMATH DE number 37729 (Why is no real title available?)
• A Quadtree-Based Dynamic Attribute Indexing Method
• scientific article; zbMATH DE number 1830754 (Why is no real title available?)
• Data structures with dynamical random transitions
• Dynamizing static algorithms, with applications to dynamic trees and history independence
• Maintaining multiple representations of dynamic data structures
• Competitive data-structure dynamization
• The design of dynamic data structures
• Dynamic data structures for realtime management of large geometric scenes (extended abstract)

This page was built for publication: On the dynamization of data structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1095647)