On the search path length of random binary skip graphs
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| dc.contributor.author | DUCHON, Philippe | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| dc.contributor.author | HUBERT, Larchevêque | |
| dc.contributor.editor | SIAM | |
| dc.date.accessioned | 2024-04-15T09:48:10Z | |
| dc.date.available | 2024-04-15T09:48:10Z | |
| dc.date.created | 2009-12-17 | |
| dc.date.issued | 2010-01-16 | |
| dc.date.conference | 2010-01-16 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/198159 | |
| dc.description.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 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é. | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.publisher | SIAM | |
| dc.subject.en | Randomized data structures | |
| dc.subject.en | analysis of algorithms | |
| dc.title.en | On the search path length of random binary skip graphs | |
| dc.type | Communication dans un congrès | |
| dc.subject.hal | Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC] | |
| dc.subject.hal | Informatique [cs]/Algorithme et structure de données [cs.DS] | |
| bordeaux.page | 1-8 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | ANALCO 2010 | |
| bordeaux.country | US | |
| bordeaux.conference.city | Austin | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | inria-00547935 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.conference.organizer | Golin, Mordecai and Sedgewick, Robert | |
| hal.conference.end | 2010-01-16 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//inria-00547935v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2010-01-16&rft.spage=1-8&rft.epage=1-8&rft.au=DUCHON,%20Philippe&HUBERT,%20Larchev%C3%AAque&rft.genre=unknown |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||