Data Structures on Event Graphs

Bernard Chazelle, Wolfgang Mulzer

Research output: Contribution to journalArticle

Abstract

We investigate the behavior of data structures when the input and operations are generated by an event graph. This model is inspired by Markov chains. We are given a fixed graph G, whose nodes are annotated with operations of the type insert, delete, and query. The algorithm responds to the requests as it encounters them during a (random or adversarial) walk in G. We study the limit behavior of such a walk and give an efficient algorithm for recognizing which structures can be generated. We also give a near-optimal algorithm for successor searching if the event graph is a cycle and the walk is adversarial. For a random walk, the algorithm becomes optimal.

Original languageEnglish (US)
Pages (from-to)1007-1020
Number of pages14
JournalAlgorithmica
Volume71
Issue number4
DOIs
StatePublished - Jan 1 2015

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Data Structure
  • Low entropy
  • Markov Chain
  • Successor searching

Fingerprint Dive into the research topics of 'Data Structures on Event Graphs'. Together they form a unique fingerprint.

  • Cite this