%0 Conference Paper %1 Brinkhoff93efficientprocessing %A Brinkhoff, Thomas %A peter Kriegel, Hans %A Seeger, Bernhard %D 1993 %K indexing r-tree spatial tree %P 237--246 %T Efficient Processing of Spatial Joins Using R-Trees %U http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.72.4514 %X Abstract: In this paper, we show that spatial joins are very suitable to be processed on a parallel hardware platform. The parallel system is equipped with a so-called shared virtual memory which is well-suited for the design and implementation of parallel spatial join algorithms. We start with an algorithm that consists of three phases: task creation, task assignment and parallel task execu-tion. In order to reduce CPU- and I/O-cost, the three phases are processed in a fashion that pre-serves spatial locality. Dynamic load balancing is achieved by splitting tasks into smaller ones and reassigning some of the smaller tasks to idle processors. In an experimental performance compar-ison, we identify the advantages and disadvantages of several variants of our algorithm. The most efficient one shows an almost optimal speed-up under the assumption that the number of disks is sufficiently large. Topics: spatial database systems, parallel database systems 1

@inproceedings{Brinkhoff93efficientprocessing, abstract = {Abstract: In this paper, we show that spatial joins are very suitable to be processed on a parallel hardware platform. The parallel system is equipped with a so-called shared virtual memory which is well-suited for the design and implementation of parallel spatial join algorithms. We start with an algorithm that consists of three phases: task creation, task assignment and parallel task execu-tion. In order to reduce CPU- and I/O-cost, the three phases are processed in a fashion that pre-serves spatial locality. Dynamic load balancing is achieved by splitting tasks into smaller ones and reassigning some of the smaller tasks to idle processors. In an experimental performance compar-ison, we identify the advantages and disadvantages of several variants of our algorithm. The most efficient one shows an almost optimal speed-up under the assumption that the number of disks is sufficiently large. Topics: spatial database systems, parallel database systems 1}, added-at = {2013-09-06T14:21:29.000+0200}, author = {Brinkhoff, Thomas and peter Kriegel, Hans and Seeger, Bernhard}, biburl = {https://www.bibsonomy.org/bibtex/21dd4dc65393e73bb15a3a511a2fc45b0/schwemmlein}, description = {CiteSeerX — Efficient Processing of Spatial Joins Using R-Trees}, interhash = {f42062ef5ef912b0a936a37196b8d8e0}, intrahash = {1dd4dc65393e73bb15a3a511a2fc45b0}, keywords = {indexing r-tree spatial tree}, pages = {237--246}, timestamp = {2013-09-06T14:21:29.000+0200}, title = {Efficient Processing of Spatial Joins Using R-Trees}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.72.4514}, year = 1993 }