Abstract
The basic concept for processing spatial joins consists of two steps: First, the spatial join is performed on the minimum bounding rectangles of the objects by using a spatial access method. This step provides a set of candidates which consists of answers (hits) and non-answers (false hits). In the second step, the exact geometry of the candidates is transferred from secondary storage into main memory and is tested against the join predicate. This step is called refinement step. It causes the main cost for computing a spatial join. In this paper, we introduce an additional filter step in order to reduce the cost of the refinement step. In this filter step more sophisticated approximations are used to identify hits as well as to filter out false hits from the set of candidates. For this purpose, we investigate various types of conservative and progressive approximations. The performance of the approximation approach is evaluated with data sets from real cartographic applications. The results show that this approach considerably reduces the total execution time of the spatial join.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Asano Ta., Asano Te.: ‘Minimum Partition of Polygonal Regions into Trapezoids', Proc. 24th IEEE Annual Symp. on Foundations of Computer Science, 1983, pp. 233–241.
Blankenagel G., Güting H.: ‘Internal and External Algorithms for the Points-in-Regions Problem — the INSIDE Join of Geo-Relational Algebra', Algorithmica, 1990, pp. 251–276.
Becker L., Hinrichs K., Finke U.: ‘A New Algorithm for Computing Joins with Grid Files', Proc. 9th Int. Conf. on Data Engineering, Vienna, Austria, 1993, pp. 190–197.
Brinkhoff T., Kriegel H.-P.: ‘The Impact of Global Clustering on Spatial Database Systems', Proc. 20th Int. Conf. on Very Large Data Bases, Santiago de Chile, Sept. 1994.
Brinkhoff T., Kriegel H.-P., Seeger B.: ‘Efficient Processing of Spatial Joins Using R-trees', Proc. ACM SIGMOD Int. Conf. on Management of Data, Washington, DC, 1993, pp. 237–246.
Brinkhoff T., Kriegel H.-P., Schneider R.: ‘Comparison of Approximations of Complex Objects used for Approximation-based Query Processing in Spatial Database Systems', Proc. 9th Int. Conf. on Data Engineering, Vienna, Austria, 1993, pp. 40–49.
Beckmann N., Kriegel H.-P., Schneider R., Seeger B.: ‘TheR *-tree: An Efficient and Robust Access Method for Points and Rectangles', Proc. ACM SIGMOD Int. Conf. on Management of Data, Atlantic City, NJ, 1990, pp. 322–331.
Brinkhoff T., Kriegel H.-P., Schneider R., Seeger B.: ‘Multi-Step Processing of Spatial Joins', Proc. ACM SIGMOD Int. Conf. on Management of Data, Minneapolis, MN, 1994, pp. 209–220.
Fortune S. J.: ‘A Sweepline Algorithm for Voronoi Diagrams', Algorithmica, Vol. 2, 1987.
Günther, O.: ‘Efficient Computation of Spatial Joins', Proc. 9th Int. Conf. on Data Engineering, Vienna, Austria, 1993, pp. 50–59.
Hilgefort U., Schneider R.: ‘Rundablagen: Leistungsschau 47 neuer Festplatten', c't, No. 3, 1994, pp. 102–111.
Lo M.-L., Ravishankar C.V.: ‘Spatial Joins Using Seeded Trees', Proc. ACM SIGMOD Int. Conf. on Management of Data, Minneapolis, MN, 1994, pp. 209–220.
Orenstein J.A., Manola F.A.: ‘PROBE Spatial Data Modeling and Query Processing in an Image Database Application', IEEE Trans. on Software Engineering, Vol. 14, No. 5, 1988, pp. 611–629.
Orenstein J. A.: ‘Redundancy in Spatial Databases', Proc. ACM SIGMOD Int. Conf. on Management of Data, Portland, OR, 1989, pp. 294–305.
Samet H.: ‘Applications of Spatial Data Structures', Addison-Wesley, 1990.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brinkhoff, T., Kriegel, HP. (1994). Approximations for a multi-step processing of spatial joins. In: Nievergelt, J., Roos, T., Schek, HJ., Widmayer, P. (eds) IGIS '94: Geographic Information Systems. IGIS 1994. Lecture Notes in Computer Science, vol 884. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58795-0_31
Download citation
DOI: https://doi.org/10.1007/3-540-58795-0_31
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58795-8
Online ISBN: 978-3-540-49105-7
eBook Packages: Springer Book Archive