SODA Conference 2017 Conference Paper
File Maintenance: When in Doubt, Change the Layout!
- Michael A. Bender
- Jeremy T. Fineman
- Seth Gilbert
- Tsvi Kopelowitz
- Pablo Montes
This paper gives a new deamortized solution to the sequential-file-maintenance problem. The data structure uses several new tools for solving this historically complicated problem. These tools include an unbalanced ternary-tree layout embedded in the sparse table, one-way rebalancing, and extra structural properties to keep interaction among rebalances to a minimum.