Characterizing history independent data structures

Jason D. Hartline, Edwin S. Hong, Alexander E. Mohr, William R. Pentney, Emily C. Rocke

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


We consider history independent data structures as proposed for study by Teague and Naor [3]. In a history independent data structure, nothing can be learned from the representation of the data structure except for what is available from the abstract data structure. We show that for the most part, strong history independent data structures have canonical representations. We also provide a natural less restrictive definition of strong history independence and characterize how it restricts allowable representations. We also give a general formula for creating dynamically resizing history independent data structures and give a related impossibility result.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings
Number of pages12
Volume2518 LNCS
StatePublished - 2002
Event13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 - Vancouver, BC, Canada
Duration: Nov 21 2002Nov 23 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2518 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


Other13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
CityVancouver, BC

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Characterizing history independent data structures'. Together they form a unique fingerprint.

Cite this