On the search path length of random binary skip graphs
Language
en
Communication dans un congrès
This item was published in
ANALCO 2010, 2010-01-16, Austin. 2010-01-16p. 1-8
SIAM
Abstract
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 ...Read more >
English Abstract
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 ...Read more >
English Keywords
Randomized data structures
analysis of algorithms