Spatial join techniques
Edwin H. Jacox, Hanan Samet · ACM Transactions on Database Systems · 2007
A variety of techniques for performing a spatial join are reviewed. Instead of just summarizing the literature and presenting each technique in its entirety, distinct components of the different techniques are described and each is decomposed into an overall framework for performing a spatial join. A typical spatial join technique consists of the following components: partitioning the data, performing internal-memory spatial joins on subsets of the data, and checking if the full polygons intersect. Each technique is decomposed into these components and each component addressed in a separate section so as to compare and contrast similar aspects of each technique. The goal of this survey is to describe the algorithms within each component in detail, comparing and contrasting competing methods, thereby enabling further analysis and experimentation with each component and allowing the best algorithms for a particular situation to be built piecemeal, or, even better, enabling an optimizer to choose which algorithms to use.
Cited by 250 works. doi:10.1145/1206049.1206056
Authors
References
- The Art of Computer Programming
- Introduction to Algorithms
- The Art of Computer Programming: Volume 3: Sorting and Searching
- R-trees
- Multidimensional binary search trees used for associative searching
- Fundamentals of interactive computer graphics
- Computational Geometry--An Introduction.
- Computational Geometry
- The design and analysis of spatial data structures
- Quad trees a data structure for retrieval on composite keys