Declustering R-Tree on Multi-Computer Architectures

dc.contributor.authorKoudas, N.en_US
dc.contributor.authorFaloutsos, Christosen_US
dc.contributor.authorKamel, Ibrahimen_US
dc.description.abstractWe study a method to decluster a spatial access method (and specifically an R-tree) on a shared-nothing multi-computer architecture [9]. Our first step is to propose a software architecture, with the top levels of the R-tree on the 'master'server' and the leaf nodes distributed across the servers. Nest, we study the optimal capacity of leaf nodes, or 'chunk size'. We express the response time on range queries as a function of the 'chunk size', and we show how to optimize it. This formula assumes that the 'chunks' are perfectly declustered. We propose to use the Hilbert curve to achieve such a good declustering.<P>Finally, we implemented our method on a network of workstations and we compared the experimental and the theoretical results. The conclusions are that (a) our formula for the response time is accurate (the maximum relative error was 30%; the typical error was in the vicinity of 10-15%) (b) the Hilbert-based declustering consistently outperforms a random declustering (c) most importantly, although the optimal chunk size depends on several factors (database size, size of the query, speed of the network), a safe choice for it is 1 page (whichever is the page size of the operating system). We show analytically and experimentally that a chunk size of 1 page gives either optimal or close to optimal results, for a wide range of the parameters.en_US
dc.format.extent881240 bytes
dc.relation.ispartofseriesISR; TR 1994-38en_US
dc.subjectparallel architecturesen_US
dc.subjectdata structuresen_US
dc.subjectSystems Integrationen_US
dc.titleDeclustering R-Tree on Multi-Computer Architecturesen_US
dc.typeTechnical Reporten_US


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
860.59 KB
Adobe Portable Document Format