### 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 | |

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 | Japan |

City | Kyoto |

Period | 1/17/12 → 1/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