VLDBJ'09 (abstract)
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.
Retourner à la liste des publications.