Confluent persistence revisited

Sébastien Collette, John Iacono, Stefan Langerman

    Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
    Title of host publicationProceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
    PublisherAssociation for Computing Machinery
    Pages593-601
    Number of pages9
    ISBN (Print)9781611972108
    DOIs
    StatePublished - 2012
    Event23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 - Kyoto, Japan
    Duration: Jan 17 2012Jan 19 2012

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

    Other

    Other23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
    CountryJapan
    CityKyoto
    Period1/17/121/19/12

    ASJC Scopus subject areas

    • Software
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'Confluent persistence revisited'. Together they form a unique fingerprint.

  • Cite this

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