|
|
|
I found this a particularly beautiful and content-rich paper. The ability to efficiently join spatial data sets is an important one. The spatial join relates objects with spatial extent based on whether their extents intersect or not. Because spatial extents, or geometries, are represented by possibly voluminous polygons, it is generally expensive to determine whether two objects intersect.
This paper explores a three-step approach to solving this problem. The idea is to represent the spatial extents by good approximations that may be more efficiently compared for intersection. This way, it is possible to divide all possible pairs of objects into three categories: pairs that definitely intersect, pairs that definitely do not intersect, and pairs that may intersect. It is then only necessary to relate the exact geometries of the latter category of pairs.
In the first step, the standard bounding rectangles of the objects are related using techniques described elsewhere. This produces a set of candidate pairs (the third category). In the second step, a variety of approximations are used on the candidate pairs in place of the bounding rectangles. Conservative as well as progressive approximations are considered, including minimum bounding 5-corners and maximum enclosed rectangles. In the third step, the exact geometries of the remaining candidate pairs are considered. The paper makes admirable use of empirical studies with real data throughout, which is particularly useful for this problem, where many design alternatives must be considered.
This paper is unusually informative and rich on content. It does a great job on both presenting the ideas and details; and combined with a nice structure and seven tables and eighteen figures, the paper is surprisingly easy to read and also a great pleasure to read.
Copyright © 1999 by the author(s). Review published with permission.