File maintenance: when in doubt, change the layout!

DOI10.1137/1.9781611974782.98zbMATH Open1410.68094OpenAlexW4235407553MaRDI QIDQ4575841FDOQ4575841

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

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

Mathematics Subject Classification ID

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

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)