Review - Efficient Processing of Spatial Joins Using R-Trees.

Timos K. Sellis: Review - Efficient Processing of Spatial Joins Using R-Trees. ACM SIGMOD Digital Review 2: (2000) BibTeX

Review

Spatial joins are one of the most important operations for combining spatial objects stored in several relations. Processing efficiently spatial joins is extremely important since it is a very costly operation, similarly to regular joins but with the addition of the fact that (a) joining multidimensional data makes the comparison more tricky, and (b) in most real-life applications the number of objects may be very high. In this paper, the authors present the first detailed study of spatial join processing using R-trees, and in particular R*-trees. Since R-trees are used for indexing spatial data, their use in performing joins is very important. The paper starts with the straightforward approach (nested loops), and presents several techniques for improving its execution time with respect to both, CPU and I/O-time. Two techniques which make use of spatial sorting and restricting the search space are presented. Moreover, the authors improve I/O-performance by determining how the required pages are read into the buffer. This is one of the issues addressed that I particularly liked in this paper: it introduces the concept of spatial locality, so that the pages required for computing an answer to the spatial join are in the buffer with high probability. This work has influenced a lot of us working in the area, by showing for the first time how buffer management issues should be taken under account, in the case of spatial indexing and spatial query processing. I also particularly liked the experimental performance comparison which went over all important factors affecting the performance of the algorithms and used real data sets.

References

[1]: Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246 BibTeX

BibTeX

Digital Review - DBLP: [Home | Search: Author, Title | Conferences | Journals]