UR Research (University of Rochester) · 1991 · 54 citations · 17 references
ComputingComputer ScienceMathematicsAlgorithmsData StructuresGame TheoryApproximation AlgorithmsCombinatorial Game TheoryData Structure AlgorithmsPersistent Data StructuresRandomized AlgorithmsRandomized ComputationPebble GamesPersistence In Data StructuresPersistence In Union-find Data StructuresRandomized Data StructuresUnion-find Analysis
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
17
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
Making data structures persistent
James R. Driscoll, Neil Sarnak, Daniel D. Sleator et al. · 1986 · 704 citations