On the search path length of random binary skip graphs

Philippe Duchon 1, 2, * Larchevêque Hubert 1, 2
* Auteur correspondant
2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Résumé : Dans ce travail, nous nous intéressons aux "skip graphs", une alternative aux "skip lists" permettant un meilleur équlibrage de charges et conçue pour être plus efficace dans un environnement distribué. Nous étendons des résultats de Devroye sur les skip lists, et prouvons que la longueur maximale d'un chemin de recherche dans un skip graph binaire aléatoire de taille n, est d'ordre log(n) avec forte probabilité.
Type de document :
Communication dans un congrès
SIAM. ANALCO 2010, Jan 2010, Austin, United States. SIAM, pp.1-8, 2010, 2010 Proceedings of the Seventh Workshop on Analytic Algorithmics and Combinatorics (ANALCO)
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00547935
Contributeur : Philippe Duchon <>
Soumis le : vendredi 17 décembre 2010 - 18:14:20
Dernière modification le : jeudi 11 janvier 2018 - 06:22:11
Document(s) archivé(s) le : jeudi 30 juin 2011 - 13:43:29

Fichier

SG_Analco10.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00547935, version 1

Collections

Citation

Philippe Duchon, Larchevêque Hubert. On the search path length of random binary skip graphs. SIAM. ANALCO 2010, Jan 2010, Austin, United States. SIAM, pp.1-8, 2010, 2010 Proceedings of the Seventh Workshop on Analytic Algorithmics and Combinatorics (ANALCO). 〈inria-00547935〉

Partager

Métriques

Consultations de la notice

236

Téléchargements de fichiers

176