Paper by Erik D. Demaine
- Paul Christiano, Erik D. Demaine, and Shaunak Kishore, “Lossless Fault-Tolerant Data Structures with Additive Overhead”, in Proceedings of the 12th Algorithms and Data Structures Symposium (WADS 2011), Brooklyn, New York, August 15–17, 2011, pages 243–254.
We develop the first dynamic data structures that tolerate δ memory
faults, lose no data, and incur only an Õ(δ) additive overhead in
overall space and time per operation. We obtain such data structures for
arrays, linked lists, binary search trees, interval trees, predecessor search,
and suffix trees. Like previous data structures, δ must be known in
advance, but we show how to restore pristine state in linear time, in parallel
with queries, making δ just a bound on the rate of memory faults. Our
data structures require Θ(δ) words of safe memory during an
operation, which may not be theoretically necessary but seems a practical
- The paper is 12 pages.
- The paper is available in PDF (206k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated January 18, 2021 by