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 to v2, this can be obtained by independent search operations in all versions in that interval in time O(log(n) (v2 - v1)), where n 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.

---

publication

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.

full version

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

Other publications by the author.