A unified access bound on comparison-based dynamic dictionaries

Mihai Bǎdoiu, Richard Cole, Erik D. Demaine, John Iacono

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)86-96
Number of pages11
JournalTheoretical Computer Science
Volume382
Issue number2
DOIs
StatePublished - Aug 31 2007

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A unified access bound on comparison-based dynamic dictionaries'. Together they form a unique fingerprint.

Cite this