Efficient processing of spatial joins using R-trees
Thomas Brinkhoff, Hans‐Peter Kriegel, Bernhard Seeger · Proceedings - ACM-SIGMOD International Conference on Management of Data · 1993
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
Cited by 576 works. doi:10.1145/170035.170075
Authors
References
- R-trees
- The R*-tree: an efficient and robust access method for points and rectangles
- The design and analysis of spatial data structures
- Computational geometry. an introduction
- Principles of geographical information systems for land resources assessment
- Spatial query processing in an object-oriented database system
- An effective way to represent quadtrees
- An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles
- A class of data structures for associative searching
- The implementation of POSTGRES