Paper by Erik D. Demaine
- Reference:
- 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.
- Abstract:
-
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.
- Comments:
- This paper is also available from ScienceDirect.
- Availability:
- 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
BibTeX file.
Last updated July 23, 2024 by
Erik Demaine.