Managing the history of dynamic data structures.

摘要

Dynamic and persistent data structures play an increasing role in several areas of computer science and engineering, such as object oriented programming, temporal databases and new parallel computation models and languages that allow historical references. A key feature to the above is the ability of efficiently reconstructing the history of evolving data structures. The first part of this thesis provides optimal solutions to such history reconstruction problems. More specifically, we start with the problem of efficiently maintaining the history of a set evolving in time, since this is the simplest data structure very often used to represent the state of a program or a database. The evolution of the set is realized by the following allowable operations on the set's state: the addition of a new element and the deletion or the value change of an existing element. We provide a lower bound for all algorithms solving this problem in space linear to the number of changes that occurred during the evolution. An algorithm achieving this bound is also presented. We proceed with the history reconstruction problem for more elaborate data structures that evolve like trees. The tree evolution is similarly realized by the addition of a new edge, and a deletion or name change of an existing one. A similar lower bound is proven for this case and an algorithm that achieves this bound is also given. The set of allowable operations is then augmented by the equivalence operation which enables two or more paths to share the same subtree underneath. All the algorithms presented here have a very fast parallel version. This observation motivated the second part of this thesis that deals with new algorithms for some classical problems in the area of parallel processing, such as parallel searching, merging and maximum finding. We prove that these parallel problems have faster solutions if the elements are taken from a known, bounded universe and arithmetic operations are allowed (together with comparisons). Many extensions and applications of the history algorithms are also presented. Finally, we conclude with a set of open problems for further research.