- Partially Persistent Binary Search Trees with Transcript Operations.
- Kim S. Larsen.
In 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 1373 of Lecture Notes in Computer Science, pages 350-363. Springer, 1998.
When balanced binary search trees are made partially persistent
using the node-copying method, updating remains efficient and
the possibility of searching efficiently for information in the past
is added to the system.
However, in database applications, it is often necessary or desirable
to produce whole transcripts of information change over time.
If we wish to obtain a transcript of information related
to some key k
from version number v1
this can be obtained by independent search operations in all
versions in that interval in time O(log(n) (v2 - v1))
is the maximum size of the search tree in that interval.
We discuss when and how this can be reduced to O(log(n) + (v2 - v1))
by maintaining one extra pointer with a version number in each node.
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
The final publication is available at link.springer.com.
Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.
Other publications by the author.