Optimization of Spatial Joins Using Filters


Veenhof, H.M. and Apers, P.M.G. and Houtsma, M.A.W. (1995) Optimization of Spatial Joins Using Filters. In: Proceedings of the 13th British National Conference on Databases: Advances in Databases (BNCOD 1995), 12-14 Jul 1995, Manchester, UK (pp. pp. 136-154).

open access
Abstract:When viewing present-day technical applications that rely on the use of database systems, one notices that new techniques must be integrated in database management systems to be able to support these applications efficiently. This paper discusses one of these techniques in the context of supporting a Geographic Information System. It is known that the use of filters on geometric objects has a significant impact on the processing of 2-way spatial join queries. For this purpose, filters require approximations of objects. Queries can be optimized by filtering data not with just one but with several filters. Existing join methods are based on a combination of filters and a spatial index. The index is used to reduce the cost of the filter step and to minimize the cost of retrieving geometric objects from disk.
In this paper we examine n-way spatial joins. Complex n-way spatial join queries require solving several 2-way joins of intermediate results. In this case, not only the profit gained from using both filters and spatial indices but also the additional cost due to using these techniques are examined. For 2-way joins of base relations these costs are considered part of physical database design. We focus on the criteria for mutually comparing filters and not on those for spatial indices. Important aspects of a multi-step filter-based n-way spatial join method are described together with performance experiments. The winning join method uses several filters with approximations that are constructed by rotating two parallel lines around the object.
Item Type:Conference or Workshop Item
Additional information:Imported from EWI/DB PMS [db-utwente:inpr:0000003089]
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Link to this item:http://purl.utwente.nl/publications/66460
Official URL:http://www.springerlink.com/content/p53364j05x416728
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page