• français
    • English
  • français 
    • français
    • English
  • Connexion
JavaScript is disabled for your browser. Some features of this site may not work without it.
Accueil

Afficher

Cette collectionPar Date de CréationAuteursTitresSujetsNoms de revueToute la baseCentres de recherche & CollectionsPar Date de CréationAuteursTitresSujetsNoms de revue

Mon compte

Connexion

Statistiques

Afficher les statistiques d'usage

Large-scale indexing of spatial data in distributed repositories: the SD-Rtree

Thumbnail
Date
2009
Indexation documentaire
Programmation, logiciels, organisation des données
Subject
Spatial indexing; Distributed structure
Nom de la revue
The VLDB Journal
Volume
18
Numéro
4
Date de publication
08-2009
Pages article
933-958
Nom de l'éditeur
Springer
DOI
http://dx.doi.org/10.1007/s00778-009-0135-4
URI
https://basepub.dauphine.fr/handle/123456789/1731
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
Rigaux, Philippe
Litwin, Witold
du Mouza, Cédric
Type
Article accepté pour publication ou publié
Résumé en anglais
We propose a scalable distributed data structure (SDDS) called SD-Rtree. We intend our structure for point, window and kNN queries over large spatial datasets distributed on clusters of interconnected servers. The structure balances the storage and processing load over the available resources, and aims at minimizing the size of the cluster. SD-Rtree generalizes the well-known Rtree structure. It uses a distributed balanced binary tree that scales with insertions to potentially any number of storage servers through splits of the overloaded ones. A user/application manipulates the structure from a client node. The client addresses the tree through its image that can be possibly outdated due to later split. This may generate addressing errors, solved by the forwarding among the servers. Specific messages towards the clients incrementally correct the outdated images. We present the building of an SD-Rtree through insertions, focusing on the split and rotation algorithms. We follow with the query algorithms. We describe then a flexible allocation protocol which allows to cope with a temporary shortage of storage resources through data storage balancing. Experiments show additional aspects of SD-Rtree and compare its behavior with a distributed quadtree. The results justify our various design choices and the overall utility of the structure.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Cette création est mise à disposition sous un contrat Creative Commons.