Confluent persistence revisited

Sébastien Collette; John Iacono; Stefan Langerman

doi:10.1137/1.9781611973099.50

Confluent persistence revisited

Sébastien Collette, John Iacono, Stefan Langerman

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English (US)
Title of host publication	Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
Publisher	Association for Computing Machinery
Pages	593-601
Number of pages	9
ISBN (Print)	9781611972108
DOIs	https://doi.org/10.1137/1.9781611973099.50
State	Published - 2012
Event	23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 - Kyoto, Japan Duration: Jan 17 2012 → Jan 19 2012

Publication series

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

Other

Other	23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
Country/Territory	Japan
City	Kyoto
Period	1/17/12 → 1/19/12

ASJC Scopus subject areas

Software
General Mathematics

Access to Document

10.1137/1.9781611973099.50

Cite this

Confluent persistence revisited. / Collette, Sébastien; Iacono, John; Langerman, Stefan.
Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. Association for Computing Machinery, 2012. p. 593-601 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Collette, S, Iacono, J & Langerman, S 2012, Confluent persistence revisited. in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 593-601, 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, 1/17/12. https://doi.org/10.1137/1.9781611973099.50

@inproceedings{b902cd3527f54dba98552797e080d51b,

title = "Confluent persistence revisited",

abstract = "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.",

author = "S{\'e}bastien Collette and John Iacono and Stefan Langerman",

year = "2012",

doi = "10.1137/1.9781611973099.50",

language = "English (US)",

isbn = "9781611972108",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "593--601",

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

note = "23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 ; Conference date: 17-01-2012 Through 19-01-2012",

}

TY - GEN

T1 - Confluent persistence revisited

AU - Collette, Sébastien

AU - Iacono, John

AU - Langerman, Stefan

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 -

Confluent persistence revisited

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this