117
As the document and history become larger, however, linear scanning (and its O(N)run-
time for a document containing Nchanges) is less appealing. One good strategy is to cache
versions by constructing a separate access structure containing only information from a par-
ticular version. Cached versions can contain information on one version or several. A large
number of strategies can be used to create cached versions:
• A new cache can be created for each new version.
• A new cache v be created periodically for whenever a certain number of versions has
been created on a certain line of development.
• A cache can be kept for the most recent versions on some set of branches of the version
tree.
Caches include their data by reference, so that a cached version has a size related to the
number of operations contributing to it, not the size of the sequence it represents. Since
versions are immutable, no update issues need to be considered, and cached versions can be
deleted at any time. A cached version can, however, speed updates significantly if it main-
tains pointers back to the full data structure, by allowing the correct location for new up-
dates to be found in the smaller cached structure, rather than the full structure.
While caching can speed the retrieval of a version, a cache that is also a linear list does
not provide for quick access to a particular point within a version. For the current VTML im-
plementation, this is not a serious problem, because of its target environment of server-
based access over the World Wide Web. VTML files with many versions reside at server ma-
chines, not user workstations.
6.3 Implementing Palimpsest
In contrast to VTML, which is intended as a client-server communication format, Palimp-
sest change structures are for use by local instances of collaborative applications. Because it
must handle online updates at individual editor instances, a Palimpsest data structure must
As the document and history become larger, however, linear scanning (and its O(N)run-
time for a document containing Nchanges) is less appealing. One good strategy is to cache
versions by constructing a separate access structure containing only information from a par-
ticular version. Cached versions can contain information on one version or several. A large
number of strategies can be used to create cached versions:
• A new cache can be created for each new version.
• A new cache v be created periodically for whenever a certain number of versions has
been created on a certain line of development.
• A cache can be kept for the most recent versions on some set of branches of the version
tree.
Caches include their data by reference, so that a cached version has a size related to the
number of operations contributing to it, not the size of the sequence it represents. Since
versions are immutable, no update issues need to be considered, and cached versions can be
deleted at any time. A cached version can, however, speed updates significantly if it main-
tains pointers back to the full data structure, by allowing the correct location for new up-
dates to be found in the smaller cached structure, rather than the full structure.
While caching can speed the retrieval of a version, a cache that is also a linear list does
not provide for quick access to a particular point within a version. For the current VTML im-
plementation, this is not a serious problem, because of its target environment of server-
based access over the World Wide Web. VTML files with many versions reside at server ma-
chines, not user workstations.
6.3 Implementing Palimpsest
In contrast to VTML, which is intended as a client-server communication format, Palimp-
sest change structures are for use by local instances of collaborative applications. Because it
must handle online updates at individual editor instances, a Palimpsest data structure must
