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.

BibTeX

@Article{Unified_TCS,
  AUTHOR        = {Mihai B\u{a}doiu and Richard Cole and Erik D. Demaine and
                   John Iacono},
  TITLE         = {A Unified Access Bound on Comparison-Based Dynamic Dictionaries},
  JOURNAL       = {Theoretical Computer Science},
  journalurl    = {https://www.journals.elsevier.com/theoretical-computer-science},
  VOLUME        = 382,
  NUMBER        = 2,
  MONTH         = {August},
  YEAR          = 2007,
  PAGES         = {86--96},
  NOTE          = {Special issue of selected papers from the 6th Latin American
                   Symposium on Theoretical Informatics, 2004.},

  doi           = {https://dx.doi.org/10.1016/J.TCS.2007.03.002},
  dblp          = {https://dblp.org/rec/journals/tcs/BadoiuCDI07},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1016/j.tcs.2007.03.002">ScienceDirect</A>.},
  replaces      = {Unified_LATIN2004},
  papers        = {Unified_LATIN2004},
  withstudent   = 1,
}

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)