File maintenance: when in doubt, change the layout!

DOI10.1137/1.9781611974782.98MaRDI QIDQ4575841zbMATH OpenOpenAlexFDO

Authors Jeremy T. Fineman, Tsvi Kopelowitz, Pablo Montes, Michael A. Bender, Seth Gilbert

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974782.98

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10)

Recommendations

• An on-line algorithm to optimize file layout in a dynamic environment
• A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time
• De-amortizing binary search trees
• Tight lower bounds for the online labeling problem
• Sequential access in splay trees takes linear time

Cited in

(2)

• Dynamic Trees with Almost-Optimal Access Cost
• The online house numbering problem: min-max online list labeling

This page was built for publication: File maintenance: when in doubt, change the layout!

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575841)