Paper by Erik D. Demaine
- Mihai Bădoiu, Richard Cole, Erik D. Demaine, and John Iacono, “A Unified Access Bound on Comparison-Based Dynamic Dictionaries”, Theoretical Computer Science, volume 382, number 2, August 2007, pages 86–96. Special issue of selected papers from the 6th Latin American Symposium on Theoretical Informatics, 2004.
We present a dynamic comparison-based search structure that supports
insertions, deletions, and searches within the unified bound. The unified
bound specifies that it is quick to access an element that is near a recently
accessed element. More precisely, if w(y) distinct elements
have been accessed since the last access to element y, and
d(x, y) denotes the rank distance between x
and y among the current set of elements, then the amortized cost
to access element x is
O(miny log [w(y) +
d(x, y) + 2]). This property generalizes the
working-set and dynamic-finger properties of splay trees.
- This paper is also available from ScienceDirect.
- The paper is available in PostScript (406k), gzipped PostScript (177k), and PDF (233k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Unified_LATIN2004 (A Simplified and Dynamic Unified Structure)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated January 4, 2022 by