On the search path length of random binary skip graphs
Langue
en
Communication dans un congrès
Ce document a été publié dans
ANALCO 2010, 2010-01-16, Austin. 2010-01-16p. 1-8
SIAM
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 ...Lire la suite >
Résumé en anglais
In this paper we consider the skip graph data structure, a load balancing alternative to skip lists, designed to perform better in a distributed environment. We extend previous results of Devroye on skip lists, and prove ...Lire la suite >
Mots clés en anglais
Randomized data structures
analysis of algorithms