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

https://hal.inria.fr/inria-00547935
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

File

SG_Analco10.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00547935, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

81

Files downloads

203