Skip to Main content Skip to Navigation
Conference papers

On the search path length of random binary skip graphs

Philippe Duchon 1, 2, * Larchevêque Hubert 1, 2 
* Corresponding author
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
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 that the maximum length of a search path in a random binary skip graph of size n is of order log n with high probability.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Philippe Duchon Connect in order to contact the contributor
Submitted on : Friday, December 17, 2010 - 6:14:20 PM
Last modification on : Saturday, June 25, 2022 - 8:29:59 PM
Long-term archiving on: : Thursday, June 30, 2011 - 1:43:29 PM


Files produced by the author(s)


  • HAL Id : inria-00547935, version 1



Philippe Duchon, Larchevêque Hubert. On the search path length of random binary skip graphs. ANALCO 2010, Golin, Mordecai and Sedgewick, Robert, Jan 2010, Austin, United States. pp.1-8. ⟨inria-00547935⟩



Record views


Files downloads