Self-Stabilizing Balancing Algorithm for Containment-Based Trees

Abstract : Containment-based trees encompass various handy structures such as B+-trees, R-trees and M-trees. They are widely used to build data indexes, range-queryable overlays, publish/subscribe systems both in centralized and distributed contexts. In addition to their versatility, their balanced shape ensures an overall satisfactory performance. Re- cently, it has been shown that their distributed implementations can be fault-resilient. However, this robustness is achieved at the cost of un-balancing the structure. While the structure remains correct in terms of searchability, its performance can be significantly decreased. In this paper, we propose a distributed self-stabilizing algorithm to balance containment-based trees.
Type de document :
[Technical Report] 2012
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger
Contributeur : Anissa Lamani <>
Soumis le : jeudi 13 décembre 2012 - 23:22:50
Dernière modification le : vendredi 7 décembre 2018 - 01:29:00
Document(s) archivé(s) le : jeudi 14 mars 2013 - 03:55:18


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00765005, version 1
  • ARXIV : 1212.3418


Evangelos Bampas, Anissa Lamani, Franck Petit, Mathieu Valero. Self-Stabilizing Balancing Algorithm for Containment-Based Trees. [Technical Report] 2012. 〈hal-00765005〉



Consultations de la notice


Téléchargements de fichiers