@article {16849,
	title = {Spatial join techniques},
	journal = {ACM Trans. Database Syst.},
	volume = {32},
	year = {2007},
	month = {2007/03//},
	abstract = {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.},
	keywords = {external memory algorithms, plane-sweep, Spatial join},
	isbn = {0362-5915},
	doi = {10.1145/1206049.1206056},
	url = {http://doi.acm.org/10.1145/1206049.1206056},
	author = {Jacox,Edwin H. and Samet, Hanan}
}
@article {16895,
	title = {Iterative spatial join},
	journal = {ACM Trans. Database Syst.},
	volume = {28},
	year = {2003},
	month = {2003/09//},
	pages = {230 - 256},
	abstract = {The key issue in performing spatial joins is finding the pairs of intersecting rectangles. For unindexed data sets, this is usually resolved by partitioning the data and then performing a plane sweep on the individual partitions. The resulting join can be viewed as a two-step process where the partition corresponds to a hash-based join while the plane-sweep corresponds to a sort-merge join. In this article, we look at extending the idea of the sort-merge join for one-dimensional data to multiple dimensions and introduce the Iterative Spatial Join. As with the sort-merge join, the Iterative Spatial Join is best suited to cases where the data is already sorted. However, as we show in the experiments, the Iterative Spatial Join performs well when internal memory is limited, compared to the partitioning methods. This suggests that the Iterative Spatial Join would be useful for very large data sets or in situations where internal memory is a shared resource and is therefore limited, such as with today{\textquoteright}s database engines which share internal memory amongst several queries. Furthermore, the performance of the Iterative Spatial Join is predictable and has no parameters which need to be tuned, unlike other algorithms. The Iterative Spatial Join is based on a plane sweep algorithm, which requires the entire data set to fit in internal memory. When internal memory overflows, the Iterative Spatial Join simply makes additional passes on the data, thereby exhibiting only a gradual performance degradation. To demonstrate the use and efficacy of the Iterative Spatial Join, we first examine and analyze current approaches to performing spatial joins, and then give a detailed analysis of the Iterative Spatial Join as well as present the results of extensive testing of the algorithm, including a comparison with partitioning-based spatial join methods. These tests show that the Iterative Spatial Join overcomes the performance limitations of the other algorithms for data sets of all sizes as well as differing amounts of internal memory.},
	keywords = {external memory algorithms, plane-sweep, Spatial databases, Spatial join},
	isbn = {0362-5915},
	doi = {10.1145/937598.937600},
	url = {http://doi.acm.org/10.1145/937598.937600},
	author = {Jacox,Edwin H. and Samet, Hanan}
}
