The Performance of Object Decomposition Techniques

The management of spatial data in applications such as graphics and image processing, geography as weil as computer aided design (CAD) imposes stringent new requirements on spatial database systems, in particular on efficient query processing of complex spatial objects. In this paper, we propose a twolevel, multi-representation query processing technique which consists of a filter and a refinement level. The efficiency of spatial query processing is improved considerably using the foilowing two design paradigms: first, divide and conquer, i.e. decomposition of complex spatial objects into more simple spatial components such as convex polygons, triangles or trapezoids, and second, application of efficient and robust spatial access methods tor simple spatial objects. The most powerful ingredient in our approach is the object decomposition. Applied to the refinement level of the query processor, it substitutes complex computational geometry algorithms by simple and fast algorithms tor simple components. In this paper, we present tour different decomposition techniques tor polygonal objects. The second part of the paper consists of an empirical performance comparison using real and synthetic data. The tour types of decomposition techniques are compared to each other and with the tradition al approach with respect to the performance of spatial query processing. This comparison points out that our approach using object decomposition is superior to tradition al query processing strategies. 1 lntroductio