hal-00091620, version 1

Data Structures with Dynamical Random Transitions

Clément Dombry ¹, Nadine Guillotin--Plantard ¹, Bruno Pincon ^2, 3, René Schott ^2, 4

Random Structures and Algorithms 28, 4 (2006) 403-426

• 1 :  Institut Camille Jordan (ICJ)
• 
  CNRS : UMR5208 – Université Claude Bernard - Lyon I – Ecole Centrale de Lyon – Institut National des Sciences Appliquées (INSA) - Lyon Bât. Jean Braconnier n° 101 43 Bd du 11 novembre 1918 69622 VILLEURBANNE CEDEX France
• 2 :  Institut Elie Cartan Nancy (IECN)
• http://www.iecn.u-nancy.fr/
  CNRS : UMR7502 – INRIA – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL) France
• 3 :  CORIDA (INRIA Nancy - Grand Est / IECN / LMAM)
• 
  INRIA – CNRS : UMR7502 – Université de Lorraine France
• 4 :  Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA)
• http://www.loria.fr
  INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL) Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex France

Références bibliographiques

• Type de publication : Articles dans des revues avec comité de lecture
• Domaine : Mathématiques/Probabilités
• Titre : Data Structures with Dynamical Random Transitions
• Résumé : 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.
• Langue du texte
  intégral : Anglais
• Journal :

  Random Structures and Algorithms
  Publisher	Wiley-Blackwell
  ISSN	1042-9832 (eISSN : 1098-2418)

• Audience : internationale
• Date de publication : 2006
• Volume : 28
• Numéro : 4
• Page, identifiant, ... : 403-426
• Mots Clés : dynamic random walks – data structures – dynamical systems – large deviation principle – random walk in random environment

• hal-00091620, version 1
• http://hal.archives-ouvertes.fr/hal-00091620
• oai:hal.archives-ouvertes.fr:hal-00091620
• Contributeur : René Schott <>
• Soumis le : Mercredi 6 Septembre 2006, 17:23:09
• Dernière modification le : Vendredi 1 Juillet 2011, 09:57:18