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
Description
CiteSeerX — Efficient Processing of Spatial Joins Using R-Trees
%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
}