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(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.

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 BibTeX file.
Last updated October 16, 2017 by Erik Demaine.