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(xy) 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(xy) + 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 March 12, 2024 by Erik Demaine.