Show simple item record

dc.contributor.authorRigaux, Philippe
dc.contributor.authorLitwin, Witold
dc.contributor.authordu Mouza, Cédric
dc.date.accessioned2009-09-17T13:31:15Z
dc.date.available2009-09-17T13:31:15Z
dc.date.issued2009
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/1731
dc.language.isoenen
dc.subjectSpatial indexingen
dc.subjectDistributed structureen
dc.subject.ddc005en
dc.titleLarge-scale indexing of spatial data in distributed repositories: the SD-Rtreeen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherCNAM;France
dc.description.abstractenWe 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.en
dc.relation.isversionofjnlnameThe VLDB Journal
dc.relation.isversionofjnlvol18en
dc.relation.isversionofjnlissue4en
dc.relation.isversionofjnldate2009-08
dc.relation.isversionofjnlpages933-958en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/s00778-009-0135-4en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record