Maintaining multiple representations of dynamic data structures

The problem of maintaining multiple representations of dynamic data structures is investigated: Suppose there are a number of processors, each having the same data structure (the so-called client structure). Then the problem arises of how to maintain these structures efficiently under insertions and deletions. We propose a strategy in which we store a central data structure in one processor, to which all other processors are connected. Updates are first “preprocessed” in the central structure. Then information obtained in this central update is sent to the client structures, where it is used to update these structures. By sending appropriate information, each client structure can be updated more efficiently than by just directly performing the update. We present several solutions to this multiple representation problem. For example, we show that a client structure can be updated in time proportional to the size of the changes in this structure.

Authors

• Michiel H.M. Smid
• Mark H. Overmars
• Leen Torenvliet
• Peter van Emde Boas

Keywords

No keywords are indexed for this paper.