Practical Persistent Data Structures

United States Military Academy, West Point NY

Investigators

Abstract

Practical Persistent Data Structures The legal phrase "status quo ante" refers to reverting to a previous state of affairs. The same concept frequently arises in computer science. For example, most word processors include an "undo" feature that nullifies the most recent changes and returns the document to its previous state. Unfortunately, most current methods of organizing data do not support the ability to revert to previous states, or at least do not do so efficiently. This research involves designing and evaluating practical techniques for supporting such an ability. Technically, a data structure is called "persistent" if updating the data structure creates a new version without destroying the old version. After the update the two versions co-exist, and future operations can refer to either or both. Persistent data structures are sometimes called immutable. Persistent data structures have applications in computational geometry, transaction processing, editing, functional programming, compilers, and many other areas. In addition, persistent data structures have several important non-algorithmic benefits, including elimination of certain families of bugs, increased security, and decreased need for synchronization among multiple processors. The objectives of this project include - inventing new persistent data structures, with an emphasis on practicality rather than merely theoretical efficiency, - extracting from these new data structures new design and analysis techniques suitable for a persistent environment, and - experimentally evaluating the practical efficiency of competing persistent data structures.