TY - GEN

T1 - Confluent persistence revisited

AU - Collette, Sébastien

AU - Iacono, John

AU - Langerman, Stefan

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2012

Y1 - 2012

N2 - It is shown how to enhance any data structure in the pointer model to make it confluently persistent, with efficient query and update times and limited space overhead. Updates are performed in O(log n) amortized time, and following a pointer takes O(log c log n) time where c is the in-degree of a node in the data structure. In particular, this proves that confluent persistence can be achieved at a logarithmic cost in the bounded in-degree model used widely in previous work. This is a O(n/ log n)-factor improvement over the previous known transform to make a data structure confluently persistent.

AB - It is shown how to enhance any data structure in the pointer model to make it confluently persistent, with efficient query and update times and limited space overhead. Updates are performed in O(log n) amortized time, and following a pointer takes O(log c log n) time where c is the in-degree of a node in the data structure. In particular, this proves that confluent persistence can be achieved at a logarithmic cost in the bounded in-degree model used widely in previous work. This is a O(n/ log n)-factor improvement over the previous known transform to make a data structure confluently persistent.

UR - http://www.scopus.com/inward/record.url?scp=84860138987&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84860138987&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973099.50

DO - 10.1137/1.9781611973099.50

M3 - Conference contribution

AN - SCOPUS:84860138987

SN - 9781611972108

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 593

EP - 601

BT - Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

PB - Association for Computing Machinery

T2 - 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

Y2 - 17 January 2012 through 19 January 2012

ER -