Abhatoo - Centre Nationale de Documentation

ierachical format and has a key structure that provides a canonical identi cation for each element of the hierarchy. In this paper we exploit these properties to devlop an archiving technique that is both ecient in its use of space and preserves the continuity of elements through versions of the database, something that is not provided by traditional minimum-edit-distance di approaches. The approach also uses timestamps. All versions of the data are merged into one hierarchy where an element appearing in multiple versions is stored only once along with a timestamp. By identifying the semantic continuity of elements and merging them into one data structure, our technique is capable of providing meaningful change descriptions, the archive allows us to easily answer certain temporal queries such as retrieval of any speci c version from the archive and nding the history of an element. This is in contrast with approaches that store a sequence of deltas where such operations may require undoing a large number of changes or signi cant reasoning with the deltas.

A suite of experiments also demonstrates that our archive does not incur any signi cant space overhead when contrasted with diapproaches. Another useful property of our approach is that we use XML format to represent hierarchical data and the resulting archive is also in XML. Hence, XML tools can be directly applied on our archive. In particular, we apply an XML compressor on our archive, and our experiments show that our compressed archive outperforms compressed di-based repositories in space eciency. We also show how we can extend our archiving tool to an external memory archiver for higher scalability and describe various index structures that can further improve the eciency of some temporal queries on our archive.