Data Structures with Dynamical Random Transitions

Clément Dombry (1) , Nadine Guillotin--Plantard (1) , Bruno Pincon (2) , René Schott (3, 4)

1 ICJ - Institut Camille Jordan
2 CORIDA - Robust control of infinite dimensional systems and applications
3 IECN - Institut Élie Cartan de Nancy
4 LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications

We present a (non-standard) probabilistic analysis of dynamic data structures whose sizes are considered dynamic random walks. The basic operations (insertion, deletion, positive and negative queries, batched insertion, lazy deletion, etc.) are time-dependent random variables. This model is a (small) step toward the analysis of these structures when the distribution of the set of histories is not uniform. As an illustration, we focus on list structures (linear lists, priority queues, and dictionaries) but the technique is applicable as well to more advanced data structures.

Mots clés: dynamic random walks; data structures; dynamical systems; large deviation principle; random walk in random environment

Domaines: Probabilités [math.PR]

Clément Dombry, Nadine Guillotin--Plantard, Bruno Pincon, René Schott. Data Structures with Dynamical Random Transitions. Random Structures and Algorithms, 2006, 28 (4), pp.403-426. ⟨10.1002/rsa.20091⟩. ⟨hal-00091620⟩