Persistence, amortization and randomization

Paul F. Dietz, Rajeev Raman

UR Research (University of Rochester) · 1991 · 54 citations · 17 references

DOIFull text

Open access

Concepts

Abstract

We explore several problems associated with persistent data structures, deriving our motivation from problems left open by Driscoll, Sarnak, Sleator and Tarjan in [15]. We exhibit simple methods to completely eliminate amortization from one of the data structures of Driscoll et. al.. We show new methods for making some data structures, including disjoint-set union-find, partially persistent in optimal time and space. We discuss some motivations for eliminating amortization from data structures in general, and explore a family of "pebble" games associated with eliminating amortization from data structures in general and from persistent data structures in particular. One relevant version of this pebble game shows that randomization may be a useful tool for elimination of amortization. The

References

17