@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 {16864,
	title = {Maintenance of K-nn and spatial join queries on continuously moving points},
	journal = {ACM Trans. Database Syst.},
	volume = {31},
	year = {2006},
	month = {2006/06//},
	pages = {485 - 536},
	abstract = {Cars, aircraft, mobile cell phones, ships, tanks, and mobile robots all have the common property that they are moving objects. A kinematic representation can be used to describe the location of these objects as a function of time. For example, a moving point can be represented by the function p(t) = \&OV0489;0 + (t - t0)\&OV0505;, where \&OV0489;0 is the start location, t0 is the start time, and \&OV0505; is its velocity vector. Instead of storing the location of the object at a given time in a database, the coefficients of the function are stored. When an object{\textquoteright}s behavior changes enough so that the function describing its location is no longer accurate, the function coefficients for the object are updated. Because the location of each object is represented as a function of time, spatial query results can change even when no transactions update the database. We present efficient algorithms to maintain k-nearest neighbor, and spatial join queries in this domain as time advances and updates occur. We assume no previous knowledge of what the updates will be before they occur. We experimentally compare these new algorithms with more straight forward adaptations of previous work to support updates. Experiments are conducted using synthetic uniformly distributed data, and real aircraft flight data. The primary metric of comparison is the number of I/O disk accesses needed to maintain the query results and the supporting data structures.},
	keywords = {<i>k</i>-nearest neighbor, continuously moving objects, materialized view maintenance, Moving object databases, Spatial join, temporal databases},
	isbn = {0362-5915},
	doi = {10.1145/1138394.1138396},
	url = {http://doi.acm.org/10.1145/1138394.1138396},
	author = {Iwerks,Glenn S. and Samet, Hanan and Smith,Kenneth P.}
}
@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}
}
