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(min_y 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)